Shtetl-Optimized

Throughout the day, Dick Lipton’s blog has hosted a phenomenal discussion of Vinay Deolalikar’s attempted proof of P≠NP (of which a new draft appeared as this blog entry was going to press).  As of this writing, the discussion seems to have led to the following two conclusions:

1. Deolalikar deserves our gratitude; he did a wonderful thing by bringing the TCS community together, in “Stone Soup” fashion, to talk about the P vs. NP problem, and also to stimulate public interest in this fascinating problem.
2. My $200,000 is safe.

See in particular this magisterial summary by Terry Tao.

For those of you who just arrived from Mars, I’d recommend starting with a BBC News piece by Victoria Gill, which by the standards of articles about P vs. NP in major news outlets, bears an amazingly close relation to reality.  Indeed, the only thing about the article that I disagreed with was the headline: “Million dollar maths puzzle sparks row.”  It’s not a row, a spat, or even a squabble: at most it’s a friendly scientific disagreement among friends.

---

As many others have already said, and as the BBC News piece hints at, the clearest reason for skepticism is (basically) that Deolalikar hasn’t convincingly explained why his approach doesn’t also prove problems are hard that are already known to be easy.  This is the simplest sanity check for any attempted proof of P≠NP: if you’re showing that an NP-complete problem like 3SAT is not in P, then your proof had better fail for related problems like 2SAT and XOR-SAT, which are known to be in P.  Everyone agrees that, if Deolalikar can’t answer this objection, the proof is toast.Unfortunately, Deolalikar has responded to pointed questions about this issue with vague promises to address it in a later draft (together with worries that the manuscript is already too long!).  This doesn’t inspire confidence: if one had really proved P≠NP, one should be able to explain immediately why the proof fails for XOR-SAT.This is far from the only problem with the writeup, but it’s a good example of the sort of basic question that Deolalikar needs to answer and hasn’t.

---

I feel incredible gratitude that Terry Tao, Timothy Gowers, Russell Impagliazzo, Avi Wigderson, Dick Lipton, Cris Moore, Ryan Williams, and other heavy-hitters of the math and CS worlds are hot on the case, and will quickly converge on what (if anything) is interesting and worthy of further study in Deolalikar’s writeup.  What that means is that those of us trying to enjoy our “summer vacations” are free to debate other issues raised in the past few days—issues that don’t involve quite so much, y’know, actual thinking.And thus I’d like to propose a blog-roundtable about the following question:

Under what circumstances, if any, is it desirable to bet publicly on scientific questions?

The responses to my $200,000 offer made it obvious that people I like and respect have wildly different views on the above question.

On one side, Bayesians and economic rationalists of all stripes seemed ecstatic.  The economist James Miller wrote:

I talk about prizes in the introductory microeconomics class I teach. I will definitely include what you have just done the next time I teach the course.  If more scientists were willing to bet their beliefs we would know a lot more about the world than we currently do.

Several complexity theorists also wrote in privately to express their gratitude:

dear scott, have you heard?  there is a P≠NP proof!  what do you think of it?  please let me know!  just kidding.  actually, this email is to thank you.  my emailbox has been flooded with emails like the above lines, and thanks to your blog, i can now reply by mentioning your blog posting (the “I’ve literally bet my house on it” one—which nonetheless may be most remembered for being the only correct use of “literally” on the internet in the past 5-10 years).

On the other side, one distinguished colleague warned that my bet might hurt the image of theoretical computer science, by focusing attention on superficial snap-judgments rather than the technical evaluation of proofs.  On this view, it’s my professional duty to make only scientific arguments in public: I should keep any personal guesses about a proof’s “probability of correctness” to myself.  Sure, if I can pinpoint the fatal flaw in Deolalikar’s paper, I should say so.  But if I can’t, I should just grin and bear it, even if journalists brush aside the experts’ boring, hard-to-explain technical reservations, and write article after cringe-inducing article exclaiming that “P≠NP HAS (APPARENTLY) BEEN PROVED!!!”

A different criticism—one that I confess took me by surprise—was that my $200,000 offer was “nasty” and “elitist,” something that eats disabled orphans for breakfast.  On reflection, though, I think I understand where this was coming from.  I felt like I was offering Deolalikar a damn sweet deal: he gets 200 grand if he’s right, and pays zilch if he’s wrong.  However, the act of offering those odds might be interpreted as a perpetual “vote of no confidence” in Deolalikar’s personal ability to prove P≠NP.

By analogy, it would be reprehensible if I offered $200,000 to any member of a particular race or gender who proved P≠NP, with the implication being that I didn’t think that race or gender was up to the challenge.  (And it would remain reprehensible, regardless of whether I eventually had to pay.)  Of course, it’s relevant that that’s nothing like what I did: instead, spurred on by a barrage of emails, I spent a sleepless night with Deolalikar’s manuscript, weighed what I understood of his arguments on one hand and what I knew of the titanic obstacles to proving P≠NP on the other, and (may Merlin help me) cast a prediction accordingly.

Nevertheless, to deal with the “nastiness” issue, I’ve decided to clarify that my $200,000 offer remains in effect until January 1, 2019.  That gives Deolalikar a couple more years to finish his current proof (plus more years for the journal refereeing and Clay prize processes), but it also makes clear that my bet is against a specific claim to have proved P≠NP, not against a person for all eternity.

(To answer the other question people kept asking me: no, my offer doesn’t extend to any potential P≠NP prover, much less to the other Clay Problems!  I’m hopeful that, within my lifetime, theoretical computer science will have advanced to the point where statements like P≠NP can be proved, and I’ll of course be elated, but not so catatonic as to make giving up my house seem completely immaterial by comparison.)

So: is it the duty of a scientist to express, in public and as a scientist, only what he or she can articulate reasons for? Or is it sometimes appropriate or even desirable for scientists to go beyond what they can verbalize, using such mechanisms as bets?  Now it’s your turn to weigh in!  I’ll be following the discussion by iPhone during a road trip through northern Israel, to the enormous annoyance of my traveling companions.

---

Update (8/12): I was hoping for some enlightening discussion about the ethics of scientific betting in general, not more comments on the real or imagined motives behind my bet. However, the actual comments I woke up to have convinced me that the critics of my bet were right. In principle, the bet seemed like a good way to answer the flood of queries about Deolalikar’s paper, and then get back to enjoying my trip. In practice, however, the way people respond to the bet depends entirely on what they think about my motives. If you don’t care about my motives, or consider them benign, then the bet probably provided a useful piece of information or (if you already knew the information) a useful corrective to hype. If, on the other hand, you think I’m arrogant, a media whore, etc., then the bet served no purpose except to confirm your beliefs.  Given the number of commenters on this blog who wish to ascribe the worst motives to me, it seems like the bet was counterproductive.PS. Arrogant I can see, but media whore? Really? Is it relevant that curious, well-meaning folks were pestering me to react to this announcement, that they clearly wouldn’t stop until I did, and that I was just trying to answer them while otherwise getting as little involved as I reasonably could?PPS. I’ve said this before, but let me say it again: I am unbelievably grateful to the “rapid response team” of mathematicians and computer scientists who dropped whatever else they were doing to delve into Deolalikar’s paper, and to report what they found on Lipton’s blog and elsewhere. Precisely because of their excellent work, there seemed to me to be little point in canceling my travel plans in order to try and duplicate their efforts.

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?

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.

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.”)

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.

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.

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.”

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.

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!