Shtetl-Optimized

I’m leaving tomorrow for a grand tour of Banff, then Israel, then Greece, then Princeton.  Blogging may be even lighter than usual.

In the meantime, my friend Michael Vassar has asked me to advertise the 2010 Singularity Summit, to be held August 14-15 in San Francisco.  Register now, because the summit is approaching so rapidly that meaningful extrapolation is all but impossible.

While I’m traveling, here’s a fun Singularity-related topic to discuss in the comments section: have you signed up to have your head (and possibly body) frozen in liquid nitrogen after you die, for possible Futurama-style resuscitation in the not-a-priori-impossible event that technology advances to the point where such things become possible?  Whatever your answer, how do you defend yourself against the charge of irrationality?

Follow

If you like math, and you don’t yet have a Math Overflow account, stop reading this post now (not right now, but by the end of the sentence) and set one up, before returning here to finish reading the post.  Math Overflow is the real deal: something that I’ve missed, dreamed about, and told my friends someone ought to set up for the last fifteen years, and that now finally actually exists.  (It was founded by Berkeley grad students and postdocs Anton Geraschenko, David Brown, and Scott Morrison.)  If you have a research-related math problem you can’t solve, you can post it there and there’s a nontrivial chance someone will solve it (or at least tell you something new), possibly within eleven minutes.  If you’re an ambitious student looking for a problem to solve, you can go there and find one (or a hundred).

To take one example, here’s a terrific complexity question asked by Timothy Gowers, about a notion of “average-case NP-completeness” different from the usual notions (if you think he’s asking about a well-studied topic, read the question more carefully).  I didn’t have a good answer, so I wrote a long, irrelevant non-answer summarizing what’s known about whether there are average-case NP-complete problems in the conventional sense.

But my real topic today is the sensitivity versus block-sensitivity problem, which I recently posted to MO in a disguised (and, dare I say, improved) form.

For non-Boolean-function-nerds, sensitivity vs. block-sensitivity is a frustrating and elusive combinatorial problem, first asked (as far as I know) by Noam Nisan and by Nisan-Szegedy around 1991.  Here’s a lovely paper by Claire Kenyon and Samuel Kutin that gives background and motivation as well as partial results.

Briefly, let f:{0,1}ⁿ→{0,1} be a Boolean function, with n input bits and 1 output bit. Then given an input x=x₁…x_n to f, the sensitivity of x, or s_x(f), is the number of bits of x that you can flip to change the value of f.  The sensitivity of f is s(f) = max_x s_x(f).  Also, the block-sensitivity of an input x, or bs_x(f), is the maximum number of disjoint sets of bits of x (called “blocks”) that you can flip to change the value of f, and the block sensitivity of f is bs(f) = max_x bs_x(f).  Clearly 1 ≤ s(f) ≤ bs(f) ≤ n for every non-constant Boolean function f.  (bs(f) is at least s(f) since you could always just take each block to have size 1.)

To give some examples, the n-bit OR function satisfies s(OR)=bs(OR)=n, since the all-zeroes input is sensitive to flipping any of the n input bits.  Likewise s(AND)=bs(AND)=n, since the all-ones input is sensitive to flipping any of the bits.  Indeed, it’s not hard to see that s(f)=bs(f) for every monotone Boolean function f.  For non-monotone Boolean functions, on the other hand, the block-sensitivity can be bigger.  For example, consider the “sortedness function”, a 4-input Boolean function f that outputs 1 if the input is 0000, 0001, 0011, 0111, 1111, 1110, 1100, or 1000, and 0 otherwise.  Then you can check that bs(f) is 3, whereas s(f) is only 2.

Here’s the question: What’s the largest possible gap between s(f) and bs(f)?  Are they always polynomially related?

What makes this interesting is that block-sensitivity is known to be polynomially related to a huge number of other interesting complexity measures: the decision-tree complexity of f, the certificate complexity of f, the randomized query complexity of f, the quantum query complexity of f, the degree of f as a real polynomial, you name it.  So if, as is conjectured, sensitivity and block-sensitivity are polynomially related, then sensitivity—arguably the most basic of all Boolean function complexity measures—ceases to be an outlier and joins a large and happy flock.

The largest known gap between sensitivity and block-sensitivity is quadratic, and is achieved by “Rubinstein’s function.”  To define this function, assume for simplicity that n is an even perfect square, and arrange the input bits into a √n-by-√n square grid.  Then we’ll set f(x)=1, if and only if there exists a row that has two consecutive 1’s and all other entries equal to 0.  You can check that bs(f)=n/2 (for consider the all-zeroes input), whereas s(f)=2√n (the worst case is when every row contains exactly one 1).

It’s a reasonable guess that Rubinstein’s function gives pretty much the largest gap possible, and how hard could that possibly be to prove?  Well, how hard could a white rabbit in front of a cave possibly be to kill?

I’ll confess to going on sensitivity versus block-sensitivity binges every couple of years since I first learned about this problem as an undergraduate at Cornell.  The last binge occurred this weekend, triggered by the strange block-sensitivity properties of my counterexample to the GLN Conjecture.  And that’s when it occurred to me to use the hyper-inter-network tools of Web 2.0, together with my power and influence here at Shtetl-Optimized, to unleash a new flood of activity on the problem.  There are at least four factors that make this problem well-suited to a collaborative math project:

1. The statement can be understood by almost anyone.  I could explain it to my parents.
2. It seems unlikely (though not impossible) that the solution will require any heavy-duty math.  What seems needed, rather, is lots of creativity to come up with new ideas specific to the problem at hand, as well as diabolical examples of Boolean functions that refute those ideas.
3. Even though the problem has been around for 20 years, the relevant literature is very small (maybe half a dozen papers); it would take at most a day to learn everything known about the problem.
4. Despite 1-3, this is a real problem that a significant number of people would care about the answer to.

If you feel like you want a new angle on the problem—something that hasn’t already been explored to death, or even to serious injury—you can try my “geometric variant” of sensitivity vs. block sensitivity described on Math Overflow.

I’m calling this a “philomath project,” a term that pays tribute to the successful polymath projects popularized by (and carried out on) Timothy Gowers’ wonderful blog, but that avoids infringing on a registered trademark of GowersCorp.

So, here are the philomath project rules: do you have an idea about sensitivity vs. block sensitivity?  Or a vague pseudo-idea?  Or a proposal for an easier variant?   Then post it here!  Or go over to Math Overflow and post it there.  Let’s see if a block of us acting in unison can flip this problem.

Follow

Does this post finally herald my return to regular blogging after a months-long absence?

I don’t know.  For me, writing a Shtetl-Optimized entry always followed the same process: I’d get an idea and start typing, furiously rocking back and forth in my chair.  Then the voices in my head would pipe up: no, I can’t say that—what will everyone think?—judging from past experience, they’ll probably take offense—I can already see the commenters boiling me alive—maybe if I rephrased it, or, y’know, provided some context—but to explain the real context, I’d need a whole book—and who has the time for that?—better wait till after tenure—meantime, maybe I could blog about something light and uncontroversial instead—but then what’s the point?—we already have one GASARCH—well, I could always put off a decision till later—

Back in the blog’s heyday, I’d win these fights about 40% the time and the voices would win about 60%.  (In other words: if you’ve ever taken offense at an entry of mine, rest assured that you haven’t even seen the half of my drafts folder.)  But now that I have an actual stake in this shabby world—students to advise and look after, a tenure case to build, conceivably even a family to start—the voices win more like 98% of the time.  And that’s why my blogging fell off.

Occasionally, though, something comes along so uncomplicatedly joyous that I feel no reservations about sharing it with the world.  Such was the case this weekend, when I was somehow called upon to represent MIT’s EECS Department in the annual “Professor Talent Show” at Campus Preview Weekend.  This is an event where six faculty members square off, taking eight minutes each to

(1) explain why their department is the coolest,
(2) crack jokes, and
(3) possibly demonstrate a musical or athletic talent.

Then, using electronic clickers, the several hundred prefrosh in attendence vote for which major carried the day.  Though I had no absolutely no talent of any kind to demonstrate, and was up against a banjo-player, violinist, and basketball-spinner among other tough competitors, for some reason EECS won!  You can see my PowerPoint slides here:

The Future of Computer Science, and Why Every Other Major Sucks By Comparison
http://www.scottaaronson.com/talks/futurecs.ppt
(You can read the jokes that go along with each slide in the slide notes at the bottom.)

Update (4/15): I hadn’t realized at all that there’s actually a video of me giving the talk!  (Click on “Part 2.”)

Follow

This holiday season, you should see Avatar and read Logicomix (if you haven’t already).  I entered both expecting to wince over scientific inaccuracies and bad dialogue, and left both in a state of catharsis that few books or movies have ever brought me to.  Both break new ground, deal with big issues in a visually stunning way, have been predictably criticized as “simplistic,” and need a sequel.

Follow

My primary link to the rest of the cosmos—my Gmail account, bqpqpoly at gmail.com—has been down for more than 36 hours.  I get a “502 Server Error” every time I try to log in, from any computer and any browser.

Any Shtetl-Optimized readers at Google: care to fix this for me? (Or is this some sort of Halloween prank, or a paternalistic attempt to force me to stop answering emails and finish my STOC submissions?)

If you need to reach me in the meantime, please write to ghh1729 at gmail.com.  (If you understand both “bqpqpoly” and “ghh1729,” I’ll even guarantee you a response.)

Update (9PM Saturday): To be clear, the issue for me is not so much the outage itself, as the lack of any acknowledgment or response from Google. (According to the Register article, even those who are paying $50 for “Premier” service can’t get through to Google’s support line, which is advertised as being 24-hour.) I would like not merely a fix, but a personal apology from Larry and Sergey, and an explanation of what steps they’re taking to uphold the “don’t be evil” creed in the future.And to the many CS majors who read this blog: is this the sort of unresponsive corporate behemoth you want to work for? 🙂

Update (4PM Sunday): OK, Google has finally acknowledged the problem.

Update (6PM Sunday): Woohoo, my email is back! But I’m missing everything from the last few days—so if you tried to mail me over the weekend, please resend. Thanks!Google claims that this problem affected only 0.001% of Gmail users. All I can say is that they picked the wrong 0.001%. 🙂

I’m pretty sure that this is the longest I went without accessing my inbox since 1994.

My revised view: Google is not an evil behemoth. They’re a good company, and would be a great one if it didn’t take hundreds of people 40 hours to get through to them when something goes extremely wrong.

Follow

I’m normally loath to announce conferences on this blog, but my friend Michael Vassar has made an offer that appeals to my vanity, desire to please, and most of all legendary business sense.  Here it is: anyone who registers for the upcoming Singularity Summit, October 3-4 in New York, can get 50% off the registration fee by mentioning this blog.

Topics on the agenda will include (I assume) the technical prospects for immortality, brain-uploading, superintelligent AIs, and the transformation of all matter in the universe into sentient computronium.  (In other words, none of that loony stuff we discuss at CS conferences, Merlin-Arthur and whatnot.)

Speakers will include Ray Kurzweil, Michael Nielsen, Robin Hanson, Eliezer Yudkowsky, David Chalmers, and several others familiar in these parts of the nerdosphere.

I’ve never been to one of these Singular shindigs before, and unfortunately can’t make this one (I’ll be visiting UC Santa Barbara and the University of Washington).  But regular readers will know that I enjoy talking with Transhumanists and Singulatarians—even if I don’t exactly share their urgency about the coming robot revolution, and worry more about the superdoofosities of today than the superintelligences of tomorrow.  I’m sure that, for some readers, the very fact that I’m willing to debate people who consider me crazy for not arranging to have my brain frozen in liquid nitrogen when I die—or that I’d advertise a conference for such people—makes me almost as far gone as the future meat-sicles themselves.  So what can I say?  Look, when I meet people who really care about the remote future, who talk about ending all the suffering in the universe like others talk about finishing an NSF proposal, who follow their chains of logic straight past the acceptably-quirky into the “childish,” “weird,” and “naïve” without even noticing the “WHAT WILL PEOPLE THINK?” danger-signs … a little twelve-year-old nerd buried deep in my psyche can’t help but rock approvingly in his chair.

The 2009 Singularity Summit: “Advancing the messianic dream of Jeremiah, Isaiah, and the other ancient Israelite prophets … this time with more overclocked RAM and less overgrilled ram.”

Follow

A year ago, I wrote a blog entry seeking summer students to create a Worldview Manager: a web application that would prompt users to state their beliefs about various statements, and then notify them if two or more answers were in “tension” with one another, giving them the chance to modify their beliefs and thereby resolve the tension.  The idea was then covered in a short piece by Lee Gomes at Forbes.com.

I ended up selecting two students: Louis Wasserman of the University of Chicago, and Leonid Grinberg of Belmont High School.  They excelled at all aspects of this project, from low-level hacking to high-level design decisions.  If there are enough young ‘uns like them, I feel better about the future of the United States.

As a result of their work, I’m pleased to announce that you can now try Worldview Manager here.

Currently, we have only a limited selection of “topic files”, all of them rather nerdy: Complexity Theory, Strong AI, the Axiom of Choice, Quantum Computing, Libertarianism, and Quantum Mechanics.  However, if there’s enough interest, we’ll probably add more topic files soon.  In the meantime, if you have any interest in contributing topic files yourself, please let me know!  It’s actually not hard.

And if you have praise, gripes, constructive feedback, nonconstructive feedback … hey, the comments section is right underneath this sentence.

Follow

Update (8/19): I’ve answered most of the remaining questions and closed this thread.  If your question wasn’t answered earlier, please check now—sorry for the delay!  And thanks to everyone who asked.

This blog was born, in part, out of existential anguish.  My starting axioms, reflected in the blog’s title, were that

1. nerds like me are hothouse plants, requiring a bizarre, historically-improbable social environment to thrive in life;
2. if such an environment ever existed, then it didn’t survive one or more major upheavals of the twentieth century, such as the sexual revolution, the Holocaust, or the end of the Cold War;
3. I and other nerds were therefore essentially walking fossils, absurdly maladapted for the civilization in which we found ourselves (even, ironically, as that civilization relied more than ever on nerdly skills); and
4. all that being the case, I might as well kill some time by proving quantum complexity theorems and writing a blog full of crass jokes.

And therein lies the problem: this summer, I’ve simply been enjoying life too much to want to take time out to blog about it.  Happiness, it seems, is terrible for my literary productivity.

Still, enough people now rely on this blog for their procrastination needs that I feel a moral obligation to continue serving them.  So to overcome my own procrastination barrier, from now on I’m going to try writing entries that are basically just “requests for comment”: stones in a stone soup, with the intellectual barley, discursive salt, argumentative carrots, and dialectical beef chunks to be supplied by you, my readers.

(To a few commenters: thanks so much for the plywood, rotting raccoon carcasses, and used syringes, but the soup should be fine without them…)

To start things off, today we’re going to have another open thread.  You can ask pretty much anything; my one request is that you don’t ask for grad school or job application advice, since we already covered those things ad nauseum in two previous open threads.

Here are a few examples of things to ask me about:

1. My recent trip to the Azores for the FQXi Conference on Foundational Questions in Physics and Cosmology

2. My recent trip to Paris for the Complexity’2009 conference

3. My recent trip to Lexington, Kentucky for the Quantum Theory and Symmetries conference

4. The recent breakthrough paper by Jain, Ji, Upadhyay, and Watrous, finally proving what many in the quantum complexity world long suspected: that QIP=IP=PSPACE.  That is, quantum interactive proof systems provide no more computational power than classical ones.  (For more see this post from Lance and Steve Fenner, or this one from the Pontiff.)

5. The exciting new Polymath Project, to find (under some number-theoretic assumption) a deterministic polynomial-time algorithm for generating n-bit primes.  (Hat tip to Ryan O’Donnell.)

Oh, one other thing: while you’re welcome to ask personal questions, they’ll most likely be answered not by me but by Pablo the PSPACE Pirate.

Update (7/31): One question per person, please!

Follow

No doubt many of you already know … but for the rest, today’s xkcd comes impressively close (at least, I think it does) to solving the ancient philosophical riddle of how to convey what “being a nerd” feels like to someone cool since birth.

Follow