Shtetl-Optimized

I’m writing from the Barriers in Computational Complexity workshop in Princeton, where too many real things are happening for me to blog about nothing.  I understand that streaming video of all the talks will be up eventually; for now, a few highlights:

• On Tuesday I hosted a panel discussion on “Barrier Problems in Boolean Complexity.”  The panelists were Steve Cook, Avi Wigderson, Russell Impagliazzo, and Sasha Razborov.  We got lots of questions from the floor, about everything from whether P≠NP, to whether P vs. NP is independent of set theory, to whether the laws of physics can be understood as computer programs.  Alas, there were few to no serious disagreements among the panelists (indeed, you can probably guess their answers to the last three questions).

• I gave a talk entitled Has There Been Progress on the P vs. NP Question? (The link goes to the PowerPoint slides.)

• Ketan Mulmuley spoke about Geometric Complexity Theory (GCT), his approach to P vs. NP and related problems based on algebraic geometry and group representation theory.  For months I’ve been planning a blog post about GCT. Spurred on by people at the workshop, I might actually finish it soon.  In the meantime, those of you who can’t wait for your daily helping of plethysms, Weyl modules, G-varieties might want to check out Mulmuley’s new complexity-theoretic overview and complementary mathematical overview of GCT.

• Ben Rossman spoke about recent lower bounds in circuit complexity: an ~n^k/4 lower bound on the size of AC⁰ circuits computing the k-clique function, and (a brand-new result) an ~n^k/4 lower bound on the size of monotone circuits computing the k-clique function, even on average.

• Ran Raz gave an awesome talk on “How to Fool People to Work on Circuit Lower Bounds.”  (Answer: by giving them completely innocuous-looking mathematical problems, without telling them that the answers would imply breakthroughs in complexity theory.  Alas, presumably no one who attended Ran’s talk—or for that matter who’s reading this entry—can be fooled, since we’re in on the secret.)  In particular, Ran spoke about his STOC’08 paper on elusive functions, as well as some brand-new work on how lower-bounding the rank of explicit tensors would lead to circuit and formula size lower bounds.

Meanwhile, Lance has a superb survey article in Communications of the ACM about the status of the P vs. NP problem.

(An earlier version of this post discussed a preprint by Gus Gutoski on quantum multi-prover interactive proof systems.  That preprint has since been retracted.)

And now I bid adieu, as the next talk is starting and my laptop is running out of batteries.

Follow

Recently someone asked me how to give funnier talks.  My first response was to recoil at such an insolent question: doesn’t everyone know that at the core of my shtick lies a unique and ineffable je ne sais quoi that can’t be packaged, bottled, or resold?  But the truth was not that I couldn’t give advice; it’s that I didn’t want to.  For if everyone knew how easy it was to keep an audience at least half-awake, how would people like me maintain their edge?  By proving better theorems?  Having something new and relevant and say?  These questions answer themselves.

But because I love you, my readers, so deeply, and because I feel guilty about abandoning you for so long, I shall now publicly deconstruct the main ingredients of seminar humor, insofar as I’ve been able to find them.  (A few ingredients are specific to theoretical computer science, but most are more general.)

1. Make fun of people in the audience.  (Of course, you have to do it in such a way that they’re flattered you’re ripping them and not someone else.)
2. Ridicule bogus claims related to your topic, particularly claims that received wide currency in the popular press.  (To be honest, I do this not so much because it gets laughs—though it does—but as a small service to humanity.  If I can make one budding crackpot think twice before hitting “Submit” on a disproof of Bell’s Theorem, I will not have lived in vain.  Of course, the ridicule should always focus more on ideas than people; and even then, a few in the audience will frown on it, considering it unscientific or unprofessional.  Forty or fifty crackpots ago, I agreed with them.  It’s only experience that hardened me into a vigilante.)
3. Incorporate the audience’s shared experiences into your talk (without making a big deal of it, as if it’s the most natural thing in the world).  For example, when it comes time to trot out an Alice/Bob scenario, have yours wryly comment on a previous talk, an excursion everyone went on, a current event (like an election) that everyone actually cares about more than the talk…
4. Self-deprecate.  (“My first conjecture was falsified.  The following conjecture hasn’t yet been falsified, and is obviously true…”)
5. Say things that recognize and comment on how neurotic the thought-process of theoretical computer scientists really is, by taking that thought-process to extremes.  (“That’s off by a factor of 10^{10^120}, which is only O(1) and is therefore irrelevant.” “For years, people tried unsuccessfully to prove this sort of impossibility result was impossible.  Our result shows the impossibility of their goal.”)
6. If your field is interdisciplinary, the humor potential is almost limitless.  Are you a physicist?  Ridicule the computer scientists.  A computer scientist?  Ridicule the mathematicians.  A mathematician?  Ridicule the economists.  Chances are, enough differences in notation, terminology, assumptions, and underlying goals will arise in the talk to give you a never-ending supply of material.  “Disciplinary humor” is a more refined, intellectual variant of ethnic humor, and is effective for the same reasons.
7. Explain your results in an unusually vivid or graphic way.  (“If, at the moment of your death, your whole life flashed before you in an instant, and if while you were alive you’d performed suitable quantum computations on your own brain, then you could solve Graph Isomorphism in polynomial time.”)  This type of humor is my absolute favorite: on a plot with laughter volume on one axis and scientific content on the other, it’s way out on the upper-right-hand corner.
8. If you’re using PowerPoint, take full advantage of its comic potential: wild animations, text that pops up on the screen to question or even flat-out contradict what you’re saying, a punchline at the bottom of the slide that only gets revealed when you press a key, etc.  I love doing this because I have as much time as I need to “precompute” jokes (though I’ll then often elaborate on them extemporaneously).
9. Banter with the crowd: if someone makes a crack at your expense, always respond, and even escalate the interaction into a “staged fight” (the rest of the audience will love it).  If someone catches you in a mistake, or you don’t know the answer to a question, make a self-deprecating joke that acknowledges the situation even as it wins you sympathy points.
10. Have high energy!  Loud, lots of moving around, emotion in your voice … like you can’t wait to invite everyone along to the most exciting journey in the history of the universe.  Not only is that good practice in general (at the least, it keeps the audience from falling asleep), it also creates a general atmosphere in which it’s okay to laugh at jokes.
11. Pause a few beats before the punchline.  (You can get better at this by watching professional comics.)
12. Experiment!  If a particular joke bombs, drop it from your rotation; if it brings the house down, recycle it in future talks.  Of course, you should drop a joke once it reaches its saturation point, where much of the audience has already heard it in previous talks.  On the other hand, if this particular audience hasn’t yet heard the joke, disregard your own internal sense of its being “tired”: it could go over just as well as the first time, or better.
13. Steal ideas shamelessly from other speakers.  (I mean their humor techniques, not their results.)  Just as importantly, study the lame jokes other speakers use, so as to avoid them.  (For example, I estimate that 94% of quantum computing talks include a heavy-handed comment about someone or something being “in superposition”; this has not yet gotten a laugh.  Or the talks repeat stories about Feynman, Bohr, etc. that everyone in the audience has already heard a thousand times.)
14. Tailor your jokes to the audience’s background.  For instance, I have some jokes that work great in the US, but sink in other countries.  Or work on physicists but not computer scientists, or vice versa.
15. Make jokes about the country you’re visiting.  Of course, this is subject to common sense: I’ve been known to resort to “zed” / “aboot” jokes in Canada, scone / royalty / powdered wig jokes in England, and neutrality / yodeling jokes in Switzerland, but I usually don’t make the first joke that pops into my head when visiting Germany or Austria.
16. Take risks!  Here’s an Umeshism: if some of your jokes don’t flop, then you’re not being bold enough.  Do things that people can’t believe anyone would actually do in a talk.  Most people seem to operate under the assumption that when they’re giving a talk, they have to be less funny than in regular conversation, when the truth is the opposite.  If something comes into your head that’s funny to you, and it passes the most flimsy and cursory of offensiveness checks … out with it, and worry later about the consequences!

Three final remarks.

First, reading over the list, I can’t help but feel sheepish about how much one can do with such a crude and obvious bag of tricks.

Second, I only wish I applied this crude bag more consistently!  Particularly when I have a new result and I’m excited about the proof, I all too often ignore my own advice and lapse into boringness.  But at least I notice I’m doing it, get annoyed at myself, and resolve to be crasser, less mature, and less professional the next time around.

Third, you might feel that adding shtick to your talks makes you “shallow,” that all that should matter is the content of your results.  In the relatively rare case where you’re addressing experts in your own sub-sub-subfield, that’s probably true: you can drop the funny business and get straight to the point.  In all other cases, I’m almost certain the audience will understand your results better if you incorporate some shtick than if you don’t.  But hey—it’s up to you whether you want to address an ideal Platonic audience (“more lemmas! no irrelevant distractions! yes! harder! faster!”) or the actual flesh-and-blood hairless apes who are dozing off in the seminar room while you speak.

Follow

So, what was I doing these past few weeks that could possibly take precedence over writing ill-considered blog entries that I’d probably regret for the rest of my life?

1. On the gracious invitation of Renato Renner, I visited one of Al Einstein’s old stomping-grounds: ETH Zürich.  There I gave a physics colloquium called How Much Information Is In A Quantum State?, as well as a talk on my paper Quantum Copy-Protection and Quantum Money, which has been more than three years in the procrastinating.  Though I was only in Switzerland for three days, I found enough time to go hiking in the Swiss Alps, if by “Swiss Alps” you mean a 200-foot hill outside the theoretical physics building.  I’m quite proud of having made it through this entire trip—my first to Switzerland—without once yodeling or erupting into cries of “Riiiiiiicola!”  On the other hand, what with the beautiful architecture, excellent public transportation, and wonderful hosts, it was a struggle to maintain my neutrality.

2. On the plane to and from Switzerland, I had the pleasure of perusing Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak, which has just been published after floating around the interweb for many years.  If you’re a hardcore complexity lover, I can recommend buying a copy in the strongest terms.  The book lives up to its subtitle, concentrating almost entirely on developments within the last twenty years.  Classical complexity theorists should pay particular attention to the excellent quantum computing chapter, neither of whose authors has the slightest background in the subject.  You see, people, getting quantum right isn’t that hard, is it?  The book’s only flaw, an abundance of typos, is one that can and should be easily fixed in the next edition.

3. I then visited the National Institute of Standards and Technology—proud keepers of the meter and the kilogram—at their headquarters in Gaithersburg, MD.  There I gave my talk on Quantum Complexity and Fundamental Physics, a version of the shtick I did at the QIS workshop in Virginia.  Afterwards, I got to tour some of the most badass experimental facilities I’ve seen in a while.  (Setting standards and making precision measurements: is there anything else that sounds so boring but turns out to so not be?)  A highlight was the Center for Neutron Research, which houses what’s apparently the largest research reactor still operating in the US.  This thing has been operating since 1967, and it shoots large numbers of slow-moving neutrons in all directions so that archaeologists, chemists, physicists, etc. can feed off the trough and do their experiments.  The basic physics that’s been done there recently has included setting bounds on possible nonlinearities in the Schrödinger equation (even though any nonlinearity, no matter how small, could be used to send superluminal signals and solve NP-complete problems in polynomial time), as well as observing the photons that the Standard Model apparently predicts are emitted 2% of the time when a neutron decays.  I also got to see one of the world’s least jittery floors: using dynamical feedback, they apparently managed to make this floor ~10⁷ times less jittery than a normal floor, good enough that they can run a double-slit experiment with slow neutrons on top of it and see the interference pattern.  (Before you ask: yes, I wanted to jump on the floor, but I didn’t.  Apparently I would’ve messed it up for a day.)

I have to add: the few times I’ve toured a nuclear facility, I felt profoundly depressed by the “retro” feel of everything around me: analog dials, safety signs from the 60s…   Why are no new reactors being built in the US, even while their value as stabilization wedges becomes increasingly hard to ignore?  Why are we unwilling to reprocess spent fuel rods like France does?  Why do people pin their hopes on the remote prospect of controlled fusion, ignoring the controlled fission we’ve had for half a century?  Why, like some horror-movie character unwilling to confront an evil from the past, have we decided that a major technology possibly crucial to the planet’s survival must remain a museum piece, part of civilization’s past and not its future?  Of course, these are rhetorical questions.  While you can be exposed to more radiation flying cross-country than working at a nuclear reactor for months, while preventing a Chernobyl is as easy as using shielding and leaving on the emergency cooling system, human nature is often a more powerful force than physics.

4. Next I went to STOC’2009 in Bethesda, MD.  Let me say something about a few talks that are impossible not to say something about.  First, in what might or might not turn out to be the biggest cryptographic breakthrough in decades, Craig Gentry has proposed a fully homomorphic encryption scheme based on ideal lattices: that is, a scheme that lets you perform arbitrary computations on encrypted data without decrypting it.  Currently, Gentry’s scheme is not known to be breakable even by quantum computers—despite a 2002 result of van Dam, Hallgren, and Ip, which said that if a fully homomorphic encryption scheme existed, then it could be broken by a quantum computer.  (The catch?  Van Dam et al.’s result applied to deterministic encryption schemes; Gentry’s is probabilistic.)

Second, Chris Peikert (co-winner of the Best Paper Award) announced a public-key cryptosystem based on the classical worst-case hardness of the Shortest Vector Problem.  Previously, Regev had given such a cryptosystem based on the assumption that there’s no efficient quantum algorithm for SVP (see also here for a survey).  The latter was a striking result: even though Regev’s cryptosystem is purely classical, his reduction from SVP to breaking the cryptosystem was a quantum reduction.  What Peikert has now done is to “dequantize” Regev’s security argument by thinking very hard about it.  Of course, one interpretation of Peikert’s result is that classical crypto people no longer have to learn quantum mechanics—but a better interpretation is that they do have to learn QM, if only to get rid of it!  I eagerly await Oded Goldreich‘s first paper on quantum computing (using it purely as an intellectual tool, of course).

Third, Robin Moser (co-winner of the Best Paper Award and winner of the Best Student Paper Award) gave a mindblowing algorithmic version of the Lovász Local Lemma.  Or to put it differently, Moser gave a polynomial-time algorithm that finds a satisfying assignment for a k-SAT formula, assuming that each clause intersects at most 2^k-2 other clauses.  (It follows from the Local Lemma that such an assignment exists.)  Moser’s algorithm is absurdly simple: basically, you repeatedly pick an unsatisfied clause, and randomly set its variables so that it’s satisfied.  Then, if doing that has made any of the neighboring clauses unsatisfied, you randomly set their variables so that they’re satisfied, and so on, recursing until all the damage you’ve caused has also been fixed.  The proof that this algorithm actually halts in polynomial time uses a communication argument that, while simple, seemed so completely out of left field that when it was finished, the audience of theorists sort of let out a collective gasp, as if a giant black “QED” box were hovering in the air.

Fourth, Babai, Beals, and Seress showed that if G is a matrix group over a finite field of odd order, then the membership problem for G can be solved in polynomial time, assuming an oracle for the discrete logarithm problem.  This represents the culmination of about 25 years of work in computational group theory.  I was all pumped to announce an important consequence of this result not noted in the abstract—that the problem is therefore solvable in quantum polynomial time, because of Shor’s discrete log algorithm—but Laci, alas, scooped me on this highly nontrivial corollary in his talk.

5. Finally, I took the train up to Princeton, for a workshop on “Cryptography and Complexity: Status of Impagliazzo’s Worlds”.  (For the insufficiently nerdy: the worlds are Algorithmica, where P=NP; Heuristica, where P≠NP but the hard instances of NP-complete problems are hard to find; Pessiland, where the hard instances are easy to find but none of them can be used for cryptographic one-way functions; Minicrypt, where one-way functions do exist, enabling private-key cryptography, but not the trapdoor one-way functions needed for public-key cryptography; and Cryptomania, where trapdoor one-way functions exist, and cryptography can do pretty anything you could ask.)  I gave a talk on Impagliazzo’s worlds in arithmetic complexity, based on ongoing join work with Andy Drucker (where “ongoing” means we’re pretty sure more of our results are correct than would be expected by random guessing).

Tell you what: since it’s been a long time, feel free to ask whatever you feel like in the comments section, whether related to my journeys or not.  I’ll try to answer at least a constant fraction of questions.

Follow

One thing I’ve always liked about theoretical computer science is the number of proofs that are patently ridiculous—whose concluding steps seem to call more for a gong or cymbal than a “QED” box.  This is a property that CS theory inherited from logic, and that it shares with several other mathematical fields (though by no means all of them).  The titans of the comedy-proof genre are of course Gödel and Turing’s undecidability results, the latter of which arguably found its best expression as a poem.  But there are other examples all over the place, and many aren’t as well known as they should be.

I was reminded of this side of theory when my student Andy Drucker and I came up with yet another absurd proof: basically, a theorem that’s true for one reason if a certain algebraic problem is hard, and true for a completely different reason if the problem is easy.  We’re still writing it up, so at Andy’s request I won’t spill the joke yet.  For now, please content yourself with the following tried-and-true komedy klassics.

Theorem 1 (folklore): E (that is, the class of problems solvable in 2^O(n) time) does not equal PSPACE, the class of problems solvable in polynomial space.  (Though we have no idea how to prove which one is bigger than the other one—or that they’re incomparable, as seems most likely.)

Proof: Suppose E=PSPACE.  Then E=EXP by padding, where EXP is the class of problems solvable in 2^poly(n) time.  But that would contradict the Time Hierarchy Theorem.

Theorem 2 (classic, attributed to Levin): One can give a fixed, explicit algorithm, which finds satisfying assignments to Boolean formulas in polynomial time whenever they exist, assuming P=NP.

Proof: let M₁, M₂, … be a list of Turing machines that take a SAT instance φ as input.  The algorithm is as follows: dovetail (that is, run a step of M₁, then another step of M₁ and a step of M₂, then another step of M₁ and M₂ and a step of M₃, etc.), halting when one of the machines has output a valid satisfying assignment for φ.  If P=NP, then there’s some Turing machine M_i in the list that solves SAT, and that causes the whole algorithm to work in polynomial time assuming φ was satisfiable.  (The fact that you’re also simulating quadrillions of other machines merely slows things down by a “polynomial factor,” independent of the input size n.)

Theorem 3 (Gutfreund, Shaltiel, Ta-Shma): Let A be an algorithm that’s supposed to solve SAT in polynomial time (that is, find a satisfying assignment whenever one exists), but that actually fails on some SAT instance of size n.  Then if someone gives you the source code of A, you can, in time polynomial in n, find a specific SAT instance that actually witnesses A’s failure.

Proof: By the Cook-Levin Theorem, you can create a SAT instance φ(x) which encodes the statement, “x is a SAT instance of size n on which A fails (that is, either there’s a satisfying assignment A fails to find, or A outputs an assignment for x that isn’t satisfying).”  Then feed φ as input to A.  There are two cases: on the one hand, if A succeeds, then it’s helpfully provided you with a SAT instance on which it itself fails.  On the other hand, if A fails on φ, then φ itself is the SAT instance you were looking for.

Theorem 4 (Barak et al.): There exist programs that can’t be obfuscated—that is, for which having the actual code of the program lets you do something that you couldn’t do if you could only run the program as a subroutine.

Proof: Let P be a program that takes a string x as input, and does the following.  First, if x=a, where a is some n-bit “secret string” hardwired into P’s source code, then P(a) outputs another n-bit secret string b.  Second, if x is the source code of a program Q such that Q(a) outputs b (after some fixed number of steps, say t=O(n)), then P outputs a third secret string c.  Third, if x satisfies neither constraint, then P(x) outputs “FAIL.”  Now, given the source code of P, it’s easy to find c: just run P with its own code as input.  On the other hand, if you can only run P as a subroutine, then (unless you get extremely lucky) it will take exponential time to find any x for which P(x) outputs anything besides “FAIL.”  Hence it’s infeasible to find c by running P, and yet there’s no way to obfuscate P’s source code so as to hide c.

Theorem 5 (attributed by Razborov and Rudich to Wigderson): No natural proof can prove better than a half-exponential lower bound on the circuit complexity of the discrete logarithm problem.  (Here half-exponential refers to a function f—which exists, but can’t be described analytically—such that f(f(n)) grows exponentially with n.)

Proof Sketch: Suppose we can prove an f(n) lower bound on the circuit complexity of discrete log, using a natural proof.  Then by the definition of natural proof, there exists a 2^O(n)-time algorithm to distinguish a truly random function g:{0,1}ⁿ→{0,1} from a function with circuit size f(n).  This means that any efficiently-computable pseudorandom function family (PRFF), with seed length m=f(n), can be distinguished from a random function in exp(f^-1(m)) time.  By standard equivalence theorems in cryptography, this means that any purported one-way function—so for example, the modular exponentiation function—can be inverted in exp(f^-1(n)) time.  In other words, to prove a natural f(n) lower bound for the discrete logarithm problem, you must also discover an exp(f^-1(n))-time algorithm for the discrete logarithm problem.  As you show the discrete log problem to be harder, you simultaneously show it to be easier!  And when f is greater than half-exponential, the lower bound becomes greater than the upper bound.

What is it that makes these theorems funny?  (Alright, maybe not ha-ha funny, but at least snort-snort funny?)  This is one case where a few readers might want me to break the rule about never explaining a joke.  Theorems 1 and 2 are sort of like “you’re lost,” as an answer to the balloonist’s plea of “where am I?”: they’re logically impeccable yet tell you nothing whatsoever about what you wanted to know.  Theorems 3 and 4 are like someone who’s so hungry he devours the menu at a restaurant, not even realizing that the menu itself was listed on the menu.  They seem to involve a category mistake: a reference gluttonously repurposed as a referent only to become a reference again.  (This, of course, is the joke behind Gödel’s theorem as well.)  Theorem 5 is like a literary critic proving there’s no ‘reality’ separate from race, class, and gender biases, using arguments that are so well-grounded, even a white male plutocrat would have to concede their truth.  The case is a self-immolating one: every argument that makes it stronger necessarily makes it weaker as well.

So what’s your favorite sidesplitting proof?

Follow

As promised, here’s my report on the Quantum Information Science Workshop in Virginia, only a week or so behind schedule.

I tried to be cynical—really I did.  But despite my best efforts, somehow I went home more excited about quantum than I’ve been in a long time.

The highlight of the workshop was of course the closed, invitation-only, late-night meeting in the basement of NSF headquarters, at which a group of us hidebound quantum computing reactionaries plotted to keep the field focused on irrelevant mathematical abstractions, and to ostracize the paradigm-smashing entrepreneurial innovators who threaten our status.  I don’t think I’ve ever heard so much cackling in the space of a single evening, or so much clinking of bone goblets.  Stuff like that is why I entered the field in the first place.

But there were some other highlights as well:

[Full list of talks iz heer]

1. In his talk on quantum algorithms with polynomial speedups, Andris Ambainis called attention to a spectacular recent paper by Ben Reichardt, which characterizes the quantum query complexity of any partial or total Boolean function f (up to a logarithmic factor) as the optimal witness size of a span program for f, and also as the negative-weight quantum adversary lower bound for f.  Assuming this result is correct, it seems possible that the remaining open problems in quantum query complexity will be pulverized, one after another, by solving the associated SDPs for the optimal span programs.  (Incidentally, using Reichardt’s result, it must be possible to prove, e.g., a Ω(n^1/3/log(n)) lower bound for the quantum query complexity of the collision problem using the adversary method.  This was a longstanding open problem.  Can one say, explicitly, what the adversary matrices are in this case?)  Alas, it also seems possible that span programs will turn out to be almost as hard to analyze as quantum algorithms were…

(1+√5)/2. Despite the obvious danger to the future funding of the entire field, by some clerical error I was released from my padded cell to speak about “Quantum Complexity and Fundamental Physics”.  My “talk,” if it can be called that, was in my opinion neither rational nor integral to the workshop.

2. In her talk on blind quantum computation, Anne Broadbent (who’s also visiting MIT this week) described some beautiful new results that partly answer my Aaronson $25.00 Challenge from a year and a half ago.  The Challenge, if you recall, was whether a quantum computer can always “prove its work” to a classical skeptic who doesn’t believe quantum mechanics—or more formally, whether every problem in BQP admits an interactive protocol where the prover in BQP and the verifier is in BPP.  Anne, Joe Fitzsimons, and Elham Kashefi haven’t quite answered this question, but in a recent paper they’ve come close: they’ve shown that a quantum computer can prove its work to someone who’s almost completely classical, her only “quantum” power being to prepare individual polarized photons and send them over to the quantum computer.  Furthermore, their protocol has the amazing property that the quantum computer learns nothing whatsoever about which particular quantum computation it’s performing!  (Aharonov, Ben-Or, and Eban independently gave a protocol with the same amazing properties, except theirs requires the “classical” verifier to have a constant-sized quantum computer.)  Anne et al. also show that two quantum computers, who share entanglement but can’t communicate with each other, can prove their work to a completely classical verifier (while, again, remaining completely oblivious to what they computed).

On top of everything else, these results appear to be the first complexity-theoretic application of the measurement-based quantum computing paradigm, as well as the first “inherently quantum” non-relativizing results.  (Admittedly, we don’t yet have an oracle relative to which the blind quantum computing protocols don’t work—but the protocols rely essentially on the gate structure of the quantum circuits, and I conjecture that such an oracle exists.)

Rereading my Challenge, I noticed that “the [one-member] Committee may also choose to award smaller prizes for partial results.”  And thus, yesterday I had the pleasure of awarding Anne a crumpled $10 bill, with an additional $5 contributed by Seth Lloyd, for a grand total of $15.00 to be shared equally among Anne, Joe, and Elham.  (Update: Since I wrote that, Anne has elected to trade in for three signed and doodled-upon $5 bills.)  (Another Update: A $12, or $15-$O(1), prize shall be awarded to Dorit Aharonov, Michael Ben-Or, and Elad Eban the next time I see them.)  This is, I believe, the first time a monetary reward offered on Shtetl-Optimized has actually been paid out.

3. In a talk that was so good, you almost forgot it involved chemistry, Alán Aspuru-Guzik discussed applications of quantum complexity theory to understanding photosynthesis and the design of efficient solar cells (!).  To give you a sense of how mindblowing that is, it briefly made me wonder whether I should reread some of John Sidles’ cheerful ramblings about the coming merger of quantum systems engineering with biology in the 21^st century (of which, I predict, this very sentence will inspire dozens more).

So what then is the connection between quantum complexity theory and photosynthesis?  Well, a few of you might remember my post “Low-Hanging Fruit from Two Conjoined Trees” from years ago, which discussed the lovely result of Childs et al. that a quantum walk on two conjoined binary trees can reach a designated end vertex exponentially faster than a classical walk on the same graph.  That result interested me, among other things, because it can be shown to lead to an oracle relative to which BQP ⊄ SZK, which at the time I didn’t know how to find otherwise.  But especially given the bizarre nature of the graph needed to produce the oracle separation, I thought of this result as pretty much the prototype of an irrelevant complexity-theoretic curiosity (which, naturally, made me like it all the more).

You can probably guess where this is going.

Shown above is a light-harvesting molecule (image snagged from Alán’s slides), which apparently is efficient at concentrating light at its center for essentially the same reason the Childs et al. quantum walk reaches the target vertex exponentially faster than a classical walk: namely, because of destructive interference between the paths that point backward, toward the leaves.  According to Alán, what plants do to harvest sunlight is not entirely unrelated either (it also involves quantum coherence), and fully understanding these mechanisms in quantum information terms might conceivably be useful in designing better solar cells.  To be fair, a part of me always did suspect that quantum oracle separations would turn out to be the key to solving the world energy crisis.  I’ll point you here or here if you want to know more.

Incidentally, Alán’s talk had another, also extremely interesting part, which was about coming up with precise numerical estimates of the number of qubits you’d need to simulate the wavefunctions of (say) benzene, caffeine, and cholesterol.  (Many of us have long thought that simulating physics and chemistry will be the real application for scalable quantum computers if we ever build them, practical long before breaking RSA and ultimately more useful too.  But it’s not something we often talk about—ostensibly for lack of meaty things to say, really because we don’t know chemistry.)

4. In her talk, Dorit Aharonov posed an open problem that I now have no choice but to inflict on others, if I don’t want to feel forced to think about it myself.  So here’s her problem: how hard is it to find the ground state of a local Hamiltonian H=H₁+…+H_m (that is, a sum of k-qubit interactions, for some constant k), if we impose the constraint that the H_i‘s all commute with each other?  Clearly it’s somewhere between NP and QMA.  It might seem obvious that this problem should be in NP—to which I can only respond, prove it!

There were also lots of great talks by the experimentalists.  Having attended them, I can report with confidence that (1) they’re still trying to build a quantum computer but (2) decoherence is still a big problem.  If you want to know even more detail than I’ve just provided—or you want to know about the theory talks I didn’t mention, or more about the ones I did mention—ask away in the comments.  I can’t promise that no one will know the answer.

Follow

A commenter on my last post writes:

Scott, it’s your blog – but can’t we switch back to some QC or TCS topics?

I confess: after three years of staid, dignified posts about quantum computing and theoretical computer science, I somehow did the unthinkable, and let this once-respected blog become less about elucidating research than procrastinating from it.  Many readers, or so they tell me, rely on Shtetl-Optimized to keep abreast of the latest theoretical insights.  And rather than ask those readers whether they also rely on deep-fried Snickers bars for the Vitamin E in the peanuts, I have a moral obligation to serve them.

Fortunately for the theory-starved among you, a certain je ne sais quoi in the air last week has caused me to refocus my attention on research.  The mysterious force affected not only me, but seemingly my entire floor of the Stata Center—giving rise to a carnival-like crescendo of increasingly-frantic theorizing that ended just as inexplicably as it began, around 6:59PM Thursday night.

So today, I’m proud to post something vaguely related to science once again.  On the suggestion of Wim van Dam, I hereby announce another contest, with no prize or even possibly winner.  Your task is simple:

Come up with a catchy name for growth rates of the form 2^{n^α}, 0<α<1.

(For example, the running time of the fastest known classical factoring algorithm has this form, as does that of the fastest known algorithm for graph isomorphism.)

The word “subexponential” is often used, but should not be, since we already use it for growth rates smaller than 2^{n^α} for all α>0.

This just in: Friend-of-the-blog Greg Kuperberg, who’s always more fun than a cinder block combined with a reprimand, informs me that 2^{n^α} growth rates already have a name: stretched exponentials.  But

1. I’ve never heard that term in my life,
2. I don’t like it: it sounds like something bigger than exponential, not smaller, and
3. Having called 2^√n “subexponential” in his otherwise-great paper on a quantum algorithm for the Dihedral Hidden Subgroup Problem, for Greg to now lecture others on this issue seems like … stretching it.

So my and Wim’s challenge to the readerariat stands.

Follow

I know I’ve been gone from the shtetl too long—I even stood by as a P=NP goon performed a drive-by shooting through my comments section.  Part of the explanation, I’m ashamed to admit, is that I’ve been procrastinating by proving theorems and writing papers, rather than building up the massive corpus of blog entries on which my tenure case will undoubtedly rest.

But most of my absence has an unhappier source.  At an unknown time about three weeks ago, I crossed the Email Event Horizon—defined in General Unproductivity as the point beyond which you could literally spend your entire day answering emails, yet still have more emails at the end of the day demanding immediate attention than you had at the beginning.  Not spam or crank mail, but worthy missives from students, prospective students, high-school students, secretaries, TAs, fellow committee members, conference organizers, visit hosts, speakers, editors, co-editors, grant officers, referees, colleagues … everything, always, requiring you to do something, commit to some decision, send a title and abstract, pick dates for the trip, exercise Genuine Conscious Thought.  No one ever writes:

Please respond to the situation described above by cracking a joke, the less tasteful the better.  You will never need to deal with this matter again.

I don’t know the precise moment when I crossed the EEH—there was nothing to herald it, it felt like any other moment—but it’s obvious now that I’m in a new, unfamiliar causal region (and that, while I might have thought I’d crossed years ago, I hadn’t).  Communication from inside the EEH to the external universe is theoretically possible, but like Hawking radiation, it tends to be excruciatingly slow—and when it finally arrives, might simply regurgitate the incoming information in garbled form.

When I was a student, I used to wonder constantly about the professors who’d ignore my long, meticulously-crafted emails or fire off one-word replies, yet who might suddenly have an hour for me if I walked into their offices.  Were they senile?  Rude?  Did they secretly despise me?  Now I get it, now I understand—yet I doubt I could explain the warped spacetime Gmailometry I now inhabit to my own past self.  On the other hand, the recognition of what’s happened is itself a sort of liberation.  I’m starting to grasp what’s long been obvious to many of you, those who crossed the EEH before I got my first AOL account in seventh grade: that it’s useless to struggle.  By definition, the speed required to escape the EEH exceeds that of typing, while the mental energy required to accelerate a massive, resting theorist to such a speed is infinite.  So there’s nothing to do but blog, goof off, prove theorems, let the starred-but-unanswered inquiries pile higher and higher, and await the Email Singularity in my causal future.

Follow

A little-known discipline of science called computational intractability studies the boundaries of our understanding – not questions of the philosophical realm (Is there a god? An afterlife?) but of the everyday computational realm.

So says the Boston Globe, in an article that’s finally appeared, after it apparently kept getting bumped for personal health stories (I guess NP-completeness still doesn’t move papers like cancer).  I’m gratified: in this time of economic crisis, the world urgently needs more articles about what humans still won’t be able to do in a billion years.  (A colleague complained to me that computational intractability is not “little-known”; in fact, almost all computer scientists know what it is.  I’m not sure if he was joking.)

Speaking of Public Understanding of Science: as you may have heard, much of the future of American science now hinges on whether the Senate, as it haggles over the $800B stimulus, decides to sprinkle a breadcrumb or two off the table for us.  If there was ever a time to email your Senator’s office, and have a staff person check a box marked “constituent complaining about science funding” in your name, it’s probably this week.  The APS has drafted a letter for you.

Follow

Today I continue a three-entry streak of praising things that are good.  While visiting IAS to give a talk, I noticed on several of my friends’ desks heavily-bookmarked copies of the Princeton Companion to Mathematics: a 1000-page volume that’s sort of an encyclopedia of math, history of math, biographical dictionary of math, beginners’ guide to math, experts’ desk reference of math, philosophical treatise on math, cultural account of math, and defense of math rolled into one, written by about 130 topic specialists and edited by the Fields medalist, blogger, and master expositor Timothy Gowers.

The best way I can explain what the PCM is trying to do is this.  Suppose that—like in the Hitchhiker’s Guide to the Galaxy—aliens are threatening to obliterate the earth along with all its life to make room for an interstellar highway.  But while the aliens are unresponsive to pleas for mercy, an exemption might be granted if the humans can show that, over the last four millennia, such mathematical insights as they’ve managed to attain are a credit rather than an embarrassment to their species.  To help decide the case, the aliens ask that humans send them an overview of all their most interesting mathematics, comprising no more than 1,000 of the humans’ pages.  Crucially, this overview will not be read by the aliens’ great mathematicians—who have no time for such menial jobs—but by a regional highway administrator who did passably well in math class at Zorgamak Elementary School.  So the more engaging and accessible the better.

I don’t know what our chances would be in such a situation, but I know that the PCM (suitably translated into the aliens’ language) is the book I’d want beamed into space to justify the continued existence of our species.

So what makes it good?  Two things, mainly:

1. For some strange reason I still don’t understand, it’s written as if you were supposed to read it.  Picture a stack of yellow books (), and imagine cornering the authors one by one and demanding they tell you what’s really going on, and the result might look something like this.  Admittedly, there are plenty of topics I still didn’t understand after reading about them here—Calabi-Yau manifolds, K-theory, modular forms—but even there, I gained the useful information that these things are apparently hard for me even when someone’s trying to make them easy.
2. The book is cheerfully unapologetic about throwing in wavelets, error-correcting codes, the simplex algorithm, and the Ising model alongside the greatest hits of algebra, geometry, analysis, and topology—as if no one would think to do otherwise, as if the former were part of the mathematical canon all along (as indeed they could’ve been, but for historical accident).  Nor does it dismay me that the book gives such a large role to theoretical computer science—with a 30-page chapter on complexity by Avi Wigderson and Oded Goldreich, as well as chapters on cryptography, numerical analysis, computability, and quantum computing (my tiny role was to help with the last).  There are also essays on computer-assisted proofs, “experimental mathematics,” innumeracy, math and art, and the goals of mathematical research; a guide to mathematical software packages; “advice to a young mathematician”; and a timeline of mathematical events, from the first known use of a bone for counting through Shor’s factoring algorithm and the proofs of Wiles and Perelman.

But enough!  I must now descend from Platonic heaven, reenter the illusory world of shadows, and finish my grant proposal … alright, maybe one more puff …

Follow

As MIT grad student Jelani Nelson rightly pointed out to me, an historic world event took place on Tuesday, January 20—an event that many of us have awaited for decades, one that we thought we’d never live to see—and I inexcusably failed my readers by neglecting to blog about it.  The event in question, as everyone knows, was Mark Braverman posting to his web page what looks to be a proof of the Linial-Nisan Conjecture.  The LN conjecture, posed in 1990, held that

Polylog-wise independence fools AC⁰.

Alright, let me try again in English.  The conjecture says that no logic circuit, composed of a polynomial number of AND, OR, and NOT gates (of unbounded fan-in) arranged in a constant number of layers, can distinguish n input bits x₁,…,x_n that are truly random, from n input bits that look random on every subset of (say) n^0.001 bits, but that could be correlated in arbitrary ways across larger scales.  In other words, if such a circuit accepts truly random bits with probability close to 1, then it also accepts the pseudorandom bits with probability close to 1, and vice versa.  If you want to distinguish the random bits from the pseudorandom bits with noticeable bias, then you need a more powerful kind of circuit: either greater depth (say, log(n) layers instead of O(1)), or more gates (say, exponentially many), or more powerful gates (say, XOR or MAJORITY gates instead of just AND, OR, and NOT).  To a constant-depth, polynomial-size, AND/OR/NOT circuit (which we call an AC⁰ circuit for short—don’t ask why), local randomness looks just the same as global randomness.  Or so says the Linial-Nisan Conjecture.

Now, we’ve known since the eighties that AC⁰ circuits have serious limitations.  In particular, we’ve known lots of specific pseudorandom distributions that fool them.  What Linial and Nisan conjectured, and Braverman appears to have proved, is that any distribution will do the job, just so long as it “looks random locally.”

A year and a half ago, Bazzi proved the Linial-Nisan conjecture in the special case of depth-two circuits, in a 64-page tour de force.  Then Razborov gave an essentially 2-page proof of the same result.  (Need I explain how awesome that is?)  Braverman extends Bazzi’s result to circuits of any constant depth; his proof is almost as short as Razborov’s.

In proving these lower bounds, the name of the game is the polynomial method (the subject of my FOCS tutorial).  Given an AC⁰ circuit C, you first construct a low-degree real polynomial that approximates C pretty well on most inputs.  (How do you construct such a thing?  And what does “pretty well” mean?  Save it for the comments section.)  Then you observe that no low-degree polynomial could possibly distinguish a random string from a string that only looks random locally.  Why?  Because a low-degree polynomial, by definition, is a sum of local terms, and if none of those individual terms can distinguish truly random bits from pseudorandom ones (as was assumed), then their sum can’t distinguish them either, by the deep principle of the universe we call linearity of expectation.  (By contrast, an AND or OR of terms could in principle detect “global” properties of the input that none of the individual terms detected—which is why we couldn’t just apply such an argument to the AC⁰ circuit directly.)  It follows, then, that the original circuit couldn’t have distinguished local randomness from global randomness very well either, which is what we wanted to show.

So everything boils down to constructing these low-degree approximating polynomials and proving they have the right properties.  And in that context, what Braverman does is almost hilariously simple.  Given an AC⁰ circuit C, he first constructs a low-degree polynomial p that agrees with C on most inputs (from whatever fixed probability distribution you want), using the celebrated method of Valiant-Vazirani and Razborov-Smolensky.  He then observes that, when p fails to agree with C, there’s another AC⁰ circuit E, of depth slightly greater than C, that detects the failure.  Next he finds a low-degree polynomial q that approximates E in L₂-norm, using the also-celebrated 1993 theorem of Linial-Mansour-Nisan. Then he looks at p(1-q), and shows that it’s a polynomial that usually agrees with C, but when it does disagree, usually isn’t too far off.  And then … well, at that point he’s really almost done.

While I had no involvement whatsoever with this beautiful result, I’m pleased to have unwittingly set in motion a chain of events that led to it.  Since the summer, I’ve been trying to get as many lowerbounderati as possible interested in BQP versus PH, a central open problem of quantum complexity theory that’s resisted progress since the prehistoric days of 1993.  (There are certain problems that I mentally classify as “rabbits,” after the Killer Rabbit of Caerbannog from Monty Python and the Holy Grail.  BQP vs. PH is one of the fluffiest, most adorable rabbits ever to leap for my throat.)

Concretely, the goal has been to construct an oracle relative to which BQP (Bounded-Error Quantum Polynomial-time, the class of problems that are feasible for a quantum computer) is not contained in PH (the Polynomial-time Hierarchy, a generalization of NP).  Such a separation would give us probably our best evidence to date that BQP is not contained in NP—or loosely speaking, that not only can quantum computers solve certain problems exponentially faster than classical ones, they can solve certain problems exponentially faster than classical computers can even verify the answers.

(NerdNote: We do have oracles relative to which BQP⊄NP, and indeed BQP⊄MA.  But we still don’t have an oracle relative to which BQP⊄AM.  And that sticks in the craw, since we know that AM=NP under a derandomization hypothesis.)

Now, it occurred to me that BQP versus PH is closely related to the Linial-Nisan Conjecture.  That’s not quite as surprising as it sounds, since you can think of PH as the “exponentially scaled-up version” of AC⁰ … so that fighting PH ultimately boils down to fighting AC⁰.

Alright, so consider the following problem, which we’ll call Fourier Checking.  You’re given black-box access to two Boolean functions f,g:{-1,1}ⁿ→{-1,1}, and are promised that either

1. f and g were both generated uniformly at random (independently of each other), or
2. f and g were generated by first choosing a random 2ⁿ-dimensional unit vector v, then setting f(x)=sgn(v_x) and g(x)=sgn((Hv)_x), where H represents the Fourier transform over Z₂ⁿ.

The problem is to decide which, with small probability of error.

It’s not hard to see that Fourier Checking is in BQP (i.e., is efficiently solvable by a quantum computer).  For to solve it, you just go into a uniform superposition over all x∈{-1,1}ⁿ, then query f, apply a Quantum Fourier Transform, query g, and see if you’re left with (1) random garbage or (2) something close to the uniform superposition that you started with.

On the other hand, one can show that:

• A certain generalization of Bazzi’s Theorem (from “local randomness” to “local almost-randomness”—as usual, ask in the comments section) would imply that Fourier Checking is not in an important subclass of PH called AM (for “Arthur-Merlin”).  And thus, we’d get an oracle relative to which BQP⊄AM.
• The analogous generalization of the full Linial-Nisan Conjecture would imply that Fourier Checking is not in PH.  And thus, we’d get our long-sought oracle relative to which BQP⊄PH.

After realizing the above, I tried for months to prove the requisite generalization of Bazzi’s Theorem—or better yet, get someone else to prove it for me.  But I failed.  All I managed to do was to goad Razborov into proving his amazing 2-page version of Bazzi’s original theorem, which in turn inspired Braverman to shoot for the full Linial-Nisan Conjecture.

In what appears to be a cosmic prank, about the only conjectures in this area that still haven’t been proved are the ones I needed for the quantum computing problem.  And thus, I will offer $100 for a proof that Fourier Checking is not in AM, $200 for a proof that it’s not in PH.  In so doing, my hope is to make Tuesday, January 20, 2009 remembered by all as the day our economy finally got back on track.

Follow