Shtetl-Optimized

Five years ago, not long after the founding of Shtetl-Optimized, I blogged about Alex Halderman: my best friend since seventh grade at Newtown Junior High School, now a famous security researcher and a computer science professor at the University of Michigan, and someone whose exploits seem to be worrying at least one government as much as Julian Assange’s.

In the past, Alex has demonstrated the futility of copy-protection schemes for music CDs, helped force the state of California to change its standards for electronic voting machines, and led a spectacular attack against an Internet voting pilot in Washington DC.  But Alex’s latest project is probably his most important and politically-riskiest yet.  Alex, Hari Prasad of India, and Rop Gonggrijp of the Netherlands demonstrated massive security problems with electronic voting machines in India (which are used by about 400 million people in each election, making them the most widely-used voting system on earth).  As a result of this work, Hari was arrested in his home and jailed by the Indian authorities, who threatened not to release him until he revealed the source of the voting machine that he, Alex, and Rop had analyzed.  After finally being released by a sympathetic judge, Hari flew to the United States, where he received the Electronic Frontier Foundation’s 2010 Pioneer Award.  I had the honor of meeting Hari at MIT during his and Alex’s subsequent US lecture tour.

But the story continues.  Earlier this week, after flying into India to give a talk at the International Conference on Information Systems Security (ICISS’2010) in Gandhinagar, Alex and Rop were detained at the New Delhi airport and threatened with deportation from India.  No explanation was given, even though the story became front-page news in India.  Finally, after refusing to board planes out of New Delhi without being given a reason in writing for their deportation, Alex and Rop were allowed to enter India, but only on the condition that they did so as “tourists.”  In particular, they were banned from presenting their research on electronic voting machines, and the relevant conference session was cancelled.

To those in the Indian government responsible for the harassment of Alex Halderman and Rop Gonggrijp and (more seriously) the imprisonment of Hari Prasad: shame on you!  And to Alex, Hari, and Rop: let the well-wishes of this blog be like a small, nerdy wind beneath your wings.

Follow

WARNING: This post makes (what turned out in retrospect to be) advanced use of sarcasm, irony, and absurdism.  Indeed, even after I added a disclaimer explaining the sarcasm, many commenters still responded as if I actually favored gutting the National Science Foundation.  (Unless, of course, those commenters were also being sarcastic—in which case, touche!)

The confusion is completely my fault.  When I write a post, I have in my mind a reader who’s read this blog for a while, and knows that obviously I don’t favor gutting the fraction of a percentage of the Federal budget devoted to the progress of human understanding and American leadership thereof; obviously the NSF wastes plenty of money, but if it didn’t, then it would be doing a terrible job, because research is all about trying stuff that has a good chance of failure; obviously if you were seriously looking for waste, you could find orders of magnitude more of it in the military and elsewhere.  So then the only remaining question is: how can we best have fun with a disgusting and contemptible situation?  I forgot how many people come to this blog not having any idea who I am or why I’m writing—and for that, I sincerely apologize.

Now, if you’d like a sarcasm-detection challenge, I did leave lots of hints in the following post that I didn’t actually agree with Congressman Smith.  See how many of them you can find!

As some of you may have heard, the incoming Republican majority in Congress has a new initiative called YouCut, which lets ordinary Americans like me propose government programs for termination.  So imagine how excited I was to learn that YouCut’s first target—yes, its first target—was that notoriously bloated white elephant, the National Science Foundation.  Admittedly, I’ve already tried to save NSF from some wasteful expenditures, in my occasional role as an NSF panel member.  But this is my first chance to join in as a plain US citizen.

In a video explaining the new initiative, Congressman Adrian Smith concedes that the NSF supports “worthy research in the hard sciences,” but then gives two examples of NSF grants that strike him as wasteful: one involving collaboration among soccer players, the other involving modeling the sound of breaking objects.  This article gives some more detail about the projects in question.

While I can’t wait to participate, I have a few questions before I start:

1. Exactly which sciences count as “hard”?  Once the pitchforks are raised, how far do we go?  Is math fair game?  What about economics, cosmology, evolutionary biology?
2. Has there ever been a research project that couldn’t be described in such a way as to sound absurd?  (“Even in the middle of a war, university academics in Chicago are spending taxpayer dollars in a quixotic attempt to smash teeny-tiny uranium atoms underneath a football field…”)
3. Years ago, several commenters on my and Lance’s blogs eloquently argued that science funding isn’t a traditional left vs. right issue, that Republicans are at least as friendly to science as Democrats, and that viewing the modern GOP as the “party of ignorance” is inaccurate, simplistic, and offensive.  Would any of those commenters kindly help us understand what’s going on?

Let me end this post with a request: I want all of my readers to visit the YouCut page, and propose that quantum computing and theoretical computer science research be completely eliminated.  Here’s my own CAREER Award; go ahead and cite it by number as a particularly egregious example of government waste.

See, I’m hungry for the honor (not to mention the free publicity) of seeing my own favorite research topics attacked on the floor of the House.  As we all know, it’s child’s play to make fun of theoretical computer science: its abstruseness, its obvious irrelevance to national goals—however infinitesimal the cost is compared to (say) corn subsidies or defense contracts for stuff the military doesn’t want, however gargantuan the payoffs of such research have been in the past.  So what are Reps. Eric Cantor and Adrian Smith waiting for?  I dare them to do it!

Obviously, though, before the House Republicans end American participation in theoretical computer science, they’ll want to familiarize themselves with what our tiny little field actually is.  To that end, let me humbly offer the links on the sidebar to the right as one place to get started.

Update (12/18):  When a friend read this post, his first reaction was that the sarcasm would be lost on most readers.  I didn’t believe him.  See, I exist in a frame of reference wherein, when the mob shows up at your house with torches, you don’t argue with them.  Instead you say: “Oh, so you’re the ones here to burn me?  Then please, let’s get started!  There’s plenty of flammable fat around my torso area.  Do you prefer rare, medium, or well done?”  That way, at least history will record you as having gone down with your middle finger proudly aloft, rather than cowering in a corner.  However, it’s now obvious that my friend was right.  So, for the literal-minded: I think reacting to our country’s debt crisis by looking for NSF grants to ridicule is a really terrible idea, for reasons that are so self-evident I’ll simply provide some blank space for you to fill them in yourself: _______________________________.   And, having devoted my whole career to quantum computing and theoretical computer science research, I don’t wish to see them eliminated.  On the other hand, if science in United States were going to be dismantled (which, despite the efforts of some politicians, I don’t think it will be), then I’d consider it an honor for theoretical computer science to be the first in the crosshairs.

Follow

It’s time someone said it.  There exists, among a small but vocal subset of the nerd community, a strange animus against computational complexity theory, which is often rooted in factual misunderstandings, and seems wholly out of proportion to any real shortcomings that complexity theory has.  Granted, every field of science has its backseat-drivers, those extralusionary intellects who feel sure they could best the experts, but haven’t expended any actual effort in solving the problems on which the experts are stuck.  But, perhaps because of the unusual accessibility of its open problems, complexity theory seems (I might be wrong) to attract more such naysayers than other mathematical fields.

It goes without saying that no intellectual pursuit is automatically entitled to respect: it has to earn it by actual accomplishments.  But even after complexity theory delivers spectacular accomplishments—from NP-completeness to PCPs to public-key cryptography to zero-knowledge proofs to quantum computing—the carping continues unabated.  It’s this phenomenon that I’d like to understand better.

Here are the main manifestations of anti-complexitism that I’ve witnessed:

“Monday-morning quarterbacking” of complexity breakthroughs.  For an example, see this thread on Lance and Bill’s blog, which is full of knowing comments seeking to minimize Ryan Williams’s recent NEXP vs. ACC breakthrough.  Some of these comments are strangely off the mark: for example, the new result is taken to task for being “nonconstructive,” relying on the ability to perform diagonalization within the huge set NEXP.  But we’ve known since Natural Proofs that, if you want to make progress on the P vs. NP question, then you’ll need “nonconstructive” techniques that seize on a special property of the function f being lower-bounded—and diagonalization remains one of the few examples of such a technique that we have.  On the other hand, we’ve also known that, if you do use diagonalization, then you’ll need to combine it with some new ingredient to get around both the relativization and algebrization barriers.  Ryan’s proof actually does all of that, which is why many of us are so excited about it.

Refusal to accept the incremental nature of complexity theory (which is shared by every other scientific field known to humankind).  To me, one of the more humorous criticisms of Ryan’s breakthrough is that it “merely” shows NEXP is not in ACC, and not (for example) that the MAJORITY function is not in ACC.  Granted, the statement NEXP⊄ACC is pathetically weak compared to what we believe is true.  But then again, what have you done that’s advanced circuit complexity by 1% as much as this “pathetic” lower bound?

Fervent desire to see complexity theorists get their comeuppance from an “outsider.”  The anonymous blog-commentariat’s pooh-poohing of the ACC breakthrough stands in contrast to the praise that same commentariat heaped on Vinay Deolalikar’s unsuccessful attempt at proving P≠NP a few months ago.  Even though Vinay and Ryan are both academic researchers working at industry labs (HP and IBM respectively), from reading the comments, it appears part of the reason for the differing reactions is that Deolalikar was seen as more of an “outsider.”  Now, I like to root for the underdog as much as the next American, but it’s worth remembering that every scientist starts as an outsider.  It was only a decade ago that Ryan and I were both nerdy kids at Cornell, trying to get our respective crazy ideas taken seriously by professors.  To paraphrase Niels Bohr, is a “scientific insider” anything more than an outsider who’s already made most of the egregious mistakes in some subfield?

Presenting obvious, universally-known limitations of asymptotic analysis as if they were new insights.  Yes, I’m aware that a polynomial-time algorithm can be impractical because of huge constant factors or a whopping exponent.  I’m aware that an NP-complete problem can be easy on those instances that arise in practice.  Even if I have a debilitating brain injury, so that I no longer remember my own name or how to count to 10, I like to think that I’ll still be aware of these facts.  To me, dismissing complexity theory because of its love affair with worst-case, asymptotic analysis is like dismissing physics because of its love affair with frictionless surfaces, point particles, elastic collisions, and ideal springs and resistors.  In both cases, people make the simplifying assumptions not because they’re under any illusions that the world really is that way, but rather because their goal is understanding.  And in both cases, the theory itself gives you the tools to complicate your model—to put legs and hooves on your spherical cow—until you get reasonably-accurate predictions for the practical problems that interest you.  (See: D. E. Knuth, The Art of Computer Programming.)

Dismissal of complexity theory as “not real mathematics.”  There’s no denying that complexity theory is young compared to (say) complex analysis, differential equations, or Lie groups.  But if you were choosing an area to work on, why would that be a point against complexity?  It means all the more to do and discover: instead of having the elegant, unifying theory presented to you in yellow books, you get to create it!  Furthermore, we’ve seen that the connections between complexity theory and “traditional” areas of mathematics are as deep as people want to make them (and often deeper): in recent years, metric embeddings, elliptic curves, algebraic geometry, and arithmetic combinatorics have all played starring roles in complexity results.  On the other hand, yes, sometimes you can achieve a complexity breakthrough the way Ryan did, not by using “deep” mathematics, but just by thinking incredibly hard about simple facts like fast matrix multiplication and the Time Hierarchy Theorem.  Again, that’s a negative?

Attacks on complexity theory for over-reliance on conjectures, even though almost every field outside mathematics (and quite a few within mathematics) rely on conjectures as well.  This one really gets me—and is the reason why I often point out that, if we complexity theorists were physicists, we would have declared P≠NP a law of nature decades ago, then looked back with pride on our far-reaching discovery about the workings of the universe.  The problem of rigorously proving the No-SuperSearch Law would have been relegated to the mathematical physicists, much like the problem of proving the consistency of (3+1)-dimensional quantum field theory.  Instead, because we complexity theorists have the custom of trumpeting what we can’t prove from the rooftops, we give our extralusionary friends the ammunition they need to regard us as dismal failures, should they so choose.  “So you landed on the moon?  How adorable.  But tell me, why does that represent even the slightest progress toward the real goal of visiting other galaxies?”  The response, which should be obvious, is that taunting mountain-climbers for being out-of-shape laggards works best when you’re at the peak of the mountain looking down at them, not at the base looking up.  But then again, if you were climbing the mountain too, you’d be less likely to want to taunt other climbers, even those behind you: for then the competitive instincts common to all humans would have to contend with the feeling of being part of a great and difficult shared enterprise.

Follow

I usually avoid blogging about my own papers—since, as a tenure-track faculty member, I prefer to be known as a media-whoring clown who trashes D-Wave Sudoku claims, bets $200,000 against alleged P≠NP proofs, and complains about his lecture notes being appropriated by Australian actresses to sell printers.  Any research that I happen to do is best kept secret, lest it interfere with that carefully-constructed persona.

Today, though, I’m making an exception.  On Thursday, my PhD student Alex Arkhipov and I finally finished our mammoth 94 95-page preprint on The Computational Complexity of Linear Optics, which we were writing for the past year.  (Remarkably, this is Alex’s first paper.  Congratulations, Alex!)  Never before was I involved in a project that forced me to learn so many unfamiliar things, from experimental quantum optics to random matrix theory to exotic complexity classes like BPP^NP and PostBQP.  (Alright, that last one wasn’t particularly unfamiliar, but the others were.)

In one sentence, the goal of our paper is to help bridge the yawning gap between what complexity theorists believe is true about quantum mechanics—namely, that it’s exponentially-hard to simulate on a classical computer—and what experimentalists can currently demonstrate.  To do so, we try to “meet the experimentalists halfway,” by proposing a linear-optical setup that seems significantly closer to practicality than (say) a universal quantum computer, but still solves a computational problem that we can show is intractable for classical computers, under plausible and clearly-stated hardness assumptions (which don’t just amount to “our system is hard to simulate”!).

Without further ado, here’s the abstract:

We give new evidence that quantum computers — moreover, rudimentary quantum computers built entirely out of linear-optical elements — cannot be efficiently simulated by classical computers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions.

Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then P^#P=BPP^NP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation.

Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy. For this, we need two unproven conjectures: the Permanent-of-Gaussians Conjecture, which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; and the Permanent Anti-Concentration Conjecture, which says that |Per(A)|≥√(n!)/poly(n) with high probability over A. We present evidence for these conjectures, both of which seem interesting even apart from our application.

This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.

As you can see from the abstract, there’s a huge amount still to be done—of which the most obvious is (1) proving our #P-hardness conjecture and (2) doing our experiment!  I’m also hopeful that people will take up the challenge of proving similar hardness results for other “rudimentary” quantum systems, besides linear optics.  In that vein, one immediate question is whether we can give evidence that the beautiful “commuting quantum computations” model of Bremner, Jozsa, and Shepherd is hard to simulate even approximately by a classical computer.

Here are a few options for anyone who’s slightly curious about our work, but not curious enough to, y’know, download the paper:

• My PowerPoint slides.
• Alex’s PowerPoint slides, which I like better than mine.
• A MathOverflow question that I posted yesterday about the Permanent Anti-Concentration Conjecture, and which was quickly answered by Terry Tao.
• A CS Theory StackExchange question about our paper posted by András Salamon, which I answered this morning.
• New: An interesting blog post about our work by Gil Kalai.

Anyway, the main purpose of this post was simply to provide a place for people with questions about our paper to ask them.  So, shoot!

Follow

When people want to emphasize how pathetically far we are from proving P≠NP, they often use the following argument: for godsakes, we can’t even prove that NEXP-complete problems aren’t solvable by depth-3, polynomial-size circuits consisting entirely of mod 6 gates!

But no more.

As some of you may have heard, recently Ryan Williams achieved a breakthrough in circuit lower bounds.  And as a result, now we can prove that NEXP-complete problems aren’t solvable by depth-3, polynomial-size circuits consisting entirely of mod 6 gates.

More generally, Williams proves that NEXP does not have ACC circuits of third-exponential size: that is, size f(n) where f(f(f(n))) is exponential.  Here NEXP means nondeterministic exponential time (the exponential-time analogue of NP), and was long a “barrier class” for circuit lower bounds.  (Note that, if we go even slightly above NEXP, to MA_EXP, then Buhrman, Fortnow, and Thierauf proved in 1998 that MA_EXP doesn’t have polynomial-size circuits of any depth, and here the polynomial can be improved to half-exponential.)  Meanwhile, by “ACC circuits” we mean a nonuniform family of constant-depth circuits consisting of AND, OR, NOT, and MOD m gates for arbitrary positive integers m.  ACC is another “barrier class” for circuit lower bounds: if we go even slightly below it, to AC0[p] (the same as ACC, except that now we only allow MOD p gates for some fixed prime p), then we’ve known how to prove exponential circuit-size lower bounds since the work of Razborov and Smolensky in the 1980s.

To achieve the combination of NEXP and ACC, Williams implements a program proposed in his previous STOC’2010 paper, for the specific case of ACC.  At the core of his lower bound is an algorithm for deciding satisfiability of ACC circuits, which does slightly (not much) better than brute-force search.  (The algorithm relies on, of all things, fast multiplication of rectangular matrices.)  While Williams’s techniques have nothing to do with Mulmuley’s GCT program, they do fit in well with the Mulmuleyist “flip” philosophy of “proving lower bounds by proving upper bounds.”

I haven’t verified Williams’s proof, but the high-level ideas are compelling—and while the result is one of the most spectacular of the decade, it’s not so far beyond the current frontier as to strain credulity.  Suffice it to say that I won’t be betting $200,000 against this one.

Congratulations, Ryan!

Update: Amusingly, if you google Ryan Williams ACC, you get a football player of the same name who was apparently Rookie of the Year in the Atlantic Coast Conference.  Let’s all link to Ryan’s paper from our homepages, and see if we can make our “ACC Rookie of the Year” win out!

Follow

Today I’m in College Park, Maryland, for a fun quantum information workshop.  I just came from Las Vegas, where I was at FOCS 2010, appropriately held at the Monte Carlo.  (Don’t tell anyone, but I also skipped out on part of the conference for a helicopter tour of the Grand Canyon.)

However, while I’ll be happy to answer questions about either of those conferences (or about the Grand Canyon, I guess), the rest of this post won’t be about them.  Instead, it will be about some relatively approachable-looking open problems in quantum complexity theory: basically, the problems that I’d be tackling today if I were a bright-eyed grad student instead of a senile, over-the-hill 29-year-old.

The inspiration for this open problems list came from the graduate course I’m currently teaching on Quantum Complexity Theory.  Just like when I taught this class two years ago, I’m asking every student to complete a term project, either individually or in groups of two.  Here’s the thing: assigning student projects in theoretical computer science turns out to be damn hard.  Even if you make it clear that a literature survey is fine, many of the students admirably want to do something original.  But how do you come up with a theory problem that

(a) hasn’t been solved, and

(b) can be solved by someone who’s just learning the material, with a high probability of success, in 1-2 months?

And thus it is that I present my sort-of updated version of my Ten Semi-Grand Challenges for Quantum Computing Theory.  Despite the original motivation, most of these problems are probably too hard for a student term project—but all of them, I think, have term-project-sized chunks that could be ripped off.  The new challenges list makes no claim whatsoever of comprehensiveness, and is heavily skewed toward problems that I, personally, have worked on.

Without further ado, and organized into seven topics, starting with the one closest to my heart:

Quantum Query Complexity

Can we use Reichardt’s breakthrough characterization of quantum query complexity by span programs and the negative-weight adversary method to obtain new results on quantum query complexity for concrete problems?

In the quantum black-box model, if we relax the assumption that the linear transformations are unitary, and merely require that, for every Boolean input x, the sum of the squares of the “amplitudes” of the accept states is a probability (i.e., belongs to [0,1]), do we ever get an asymptotically smaller query complexity?  What about an exponentially smaller query complexity?

Given a quantum algorithm that makes T queries, can we approximate its acceptance probability on most Boolean inputs using a classical algorithm that makes poly(T) queries?  (See here for more.)

Are randomized and quantum query complexities polynomially related for all functions f(x₁,…,x_n) that are invariant under permuting the indices 1,…,n (for example, the Collision and Element Distinctness functions)?  (In previous work with Ambainis, we showed randomized and quantum query complexities are polynomially related for all functions that are invariant under permuting both the indices and the values of x₁,…,x_n.)

Can every quantum algorithm that makes k queries to an n-bit string, be simulated by a randomized algorithm that makes n^1-1/2k queries?  Does the k-fold generalization of the Fourier Checking problem provide an example for which this conjectured bound is tight?

Let f be a black-box function, which is promised to be either 1-to-1 or 2-to-1.  Is there a polylog(n)-qubit quantum proof that f is 1-to-1, which can be verified using polylog(n) quantum queries to f?  (If not, then we get an oracle relative to which SZK is not in QMA.)

Let f be a black-box function, which is promised either to satisfy the Simon promise or to be one-to-one.  Can a prover with the power of BQP convince a BPP verifier that f is one-to-one?

Cryptography

Are there interesting functionalities, besides point functions, that can be quantumly copy-protected?

Can we give classical oracles relative to which publicly-verifiable quantum money and copy-protected quantum software are possible?

Is the GGM construction of pseudorandom functions from pseudorandom generators secure even against quantum adversaries?  If not, can we give an analogous construction that’s secure?

Intermediate Possibilities Between BPP And BQP

Is it true that every set of unitary quantum gates (acting on qubits) is either universal for quantum computation, or else simulable in classical polynomial time?

If a quantum computer is in a tree state at every time step, does it follow that the computer can be simulated in classical polynomial time (i.e., in BPP)?

If a quantum computer is in a separable mixed state at every time step, does it follow that the computer can be simulated in classical polynomial time?

Postselection

Can we take any quantum computational model that allows adaptive measurements, and simulate it by a model that allows postselected measurements instead?

What are the “weakest” models of quantum computation that yield all of PostBQP when combined with postselection on measurement outcomes?

Communication Complexity

In the Group Membership Problem, there is a finite group G known to both Alice and Bob.  Alice is given a subgroup H of G,  Bob is given an element x of G, and the problem is for Bob to decide whether x is in H.  What is the randomized one-way communication complexity of GM?  Can we prove a lower-bound better than the trivial log|G|, thereby separating randomized and quantum one-way communication complexities for a total Boolean function?

Are the randomized and quantum one-way communication complexities polynomially related for every total Boolean function f?  What about the randomized and quantum two-way communication complexities?

QMA(2)

Is QMA(2) contained in EXP?  To put it differently: let V be a two-outcome measurement, which acts on the tensor product of two n-dimensional Hilbert spaces. Is there a quasipolynomial-time classical algorithm that approximates max_|ψ>[V accepts |ψ>²] to constant additive error?

Is QMA(2) with real amplitudes the same thing as QMA(2) with complex amplitudes?

Quantum Computing With Locality Constraints

Let G be a graph with n vertices, and let U be an nxn unitary matrix with the property that u_ij≠0 only if (i,j) is an edge of G.  Then how efficiently can we represent (or approximate) U as a product of unitaries that are “local” with respect to G?  This is a vague question, but see my paper with Ambainis for ways of making it precise.

Given n bits arranged in a √nx√n square grid, suppose we want to know whether every row contains at least one ‘1’ bit.  Can we do this using an ~O(√n) quantum algorithm that is “local” in the sense defined by myself and Ambainis?  Can we beat the trivial upper bound of n^3/4?

Follow

So, I’ve decided to simultaneously do something positive for theoretical computer science, stimulate BQPology research at MIT, and solve the “problem” of having too much grant money by hiring a postdoc.  The main area of interest for this postdoc is quantum complexity theory, but I’ll also consider outstanding applicants of a more classical bent—in fact, the ideal applicant is someone equally excited to tackle meaty open problems in quantum complexity, classical complexity, or any combination of the two.  As a postdoc here, you’ll collaborate (I hope) with me and my PhD students, but you’ll also have plenty of opportunities for interaction with the other quantum computing theory folks at MIT (Peter Shor, Ed Farhi, Seth Lloyd…), as well as the other computational complexity folks (too many to list).  This postdoc is for one year, with the expectation of a renewal for a second year.

If you’re interested, email your CV, a link to your homepage, and what you consider your top 3 or 4 publications to aaronson@csail.mit.edu, and also arrange to have 3 rec letters emailed to me.  Feel free to apply even if you previously applied for other postdocs at MIT: this is a new opportunity that’s somewhat different from previous ones.  The application deadline is, shall we say, December 1^st?  Let me know if you have any questions.

Finally, while I was tempted to make “reading Shtetl-Optimized” an effective prerequisite for the postdoc, feel free to distribute this call for applications more widely.

Follow

A year ago, Timothy Gowers posted the following beautiful question to MathOverflow:

Are there any interesting examples of random NP-complete problems?
Here’s an example of the kind of thing I mean. Let’s consider a random instance of 3-SAT, where you choose enough clauses for the formula to be almost certainly unsatisfiable, but not too many more than that. So now you have a smallish random formula that is unsatisfiable.

Given that formula, you can then ask, for any subset of its clauses, whether that subset gives you a satisfiable formula. That is a random (because it depends on the original random collection of clauses) problem in NP. It also looks as though it ought to be pretty hard. But proving that it is usually NP-complete also seems to be hard, because you don’t have the usual freedom to simulate.

So my question is whether there are any results known that say that some randomized problem is NP-complete. (One can invent silly artificial examples like having a randomized part that has no effect on the problem — hence the word “interesting” in the question.)

On skimming this question, my first thought was: “aha, he’s obviously groping toward the well-studied notion of average-case complexity!  Let me generously enlighten him.”  But no, it turns out he wasn’t asking about average-case complexity, but about something different and novel.  Namely, the random generation of computational problems consisting of exponentially many instances, for which we’re then interested in the worst-case instance.  When I explained to Gil Kalai what Gowers wanted, Gil amusingly described it as the “converse of smoothed analysis.”  In smoothed analysis—one of many contributions for which Dan Spielman recently won the Nevanlinna Prize—we start with a worst-case instance of a problem (such as linear programming), then perturb the instance by adding some random noise.  Gowers wants to do the opposite: start from a random instance and then perform a “worst-case perturbation” of it.  (The closest existing notions I could think of were trapdoor one-way functions and other primitives in cryptography, which involve the random generation of a computational problem that’s then supposed to be hard on average.)

Anyway, I tossed the question onto my stack of “questions that could develop into whole new branches of theoretical computer science, if someone felt like developing them,” and pretty much forgot about it.  Then, at  dinner last night, I posed the question to Allan Sly, who’s visiting MIT to talk about his exciting new FOCS paper Computational transition at the uniqueness threshold.  Within an hour, Allan had emailed me a sketch of an NP-hardness proof for the “random 3SAT” problem that Gowers asked about.  I repost Allan’s solution here with his kind permission.

Group the n variables into N=n^ε groups of size n^1-ε, M₁,…M_N arbitrarily.  For each group M_i take all the clauses with all 3 variables in M_i such that it satisfies both the all 1 and the all 0 assignments i.e. clauses that have either 1 or 2 variables negated.  I think that just a first moment estimate should show that with high probability the only assignments on M_i that satisfies all of these clauses should be the all 1 assignment or the all 0 assignment – other assignments are just too unlikely.  So in taking these clauses we reduce to the case where we have constant values on each of the groups.

Once you have these clauses you can then treat each group as a new variable and can construct any SAT assignment on these new variables.  Because now you only need to find a clause with 1 variable in each M_i, M_j, M_k for each (i,j,k) ∈ [N]³ that has the right negations. With high probability all of them should exist so you should be able to make whatever SAT assignment on the N variables you want.

My back of the envelope calculation then suggests that as long as you have n^1+ε random clauses to begin with then this should be enough.

It’s not hard to see that Allan’s solution generalizes to 3-COLORING and other constraint satisfaction problems (maybe even all NP-complete CSPs?).  In retrospect, of course, the solution is embarrassingly simple, but one could easily generate other problems in the same vein for which proving NP-hardness was as nontrivial as you wanted it to be.  Further development of this new branch of theoretical computer science, as well as coming up with a catchy name for it, are left as exercises for the reader.

Follow

As those of you in American academia have probably heard by now, this week the National Research Council finally released its 2005 rankings of American PhD programs, only five years behind schedule.  This time, the rankings have been made 80% more scientific by the addition of error bars.  Among the startling findings:

• In electrical and computer engineering, UCLA and Purdue are ahead of Carnegie Mellon.
• In computer science, UNC Chapel Hill is ahead of the University of Washington.
• In statistics, Iowa State is ahead of Berkeley.

However, before you base any major decisions on these findings, you should know that a few … irregularities have emerged in the data used to generate them.

• According to the NRC data set, 0% of graduates of the University of Washington’s Computer Science and Engineering Department had “academic plans” for 2001-2005.  (In reality, 40% of their graduates took faculty positions during that period.)  NRC also reports that UW CSE has 91 faculty (the real number is about 40).  Most of the illusory “faculty,” it turned out, were industrial colleagues who don’t supervise students, and who thereby drastically and artificially brought down the average number of students supervised.  See here and here for more from UW itself.

• According to the NRC, 0% of MIT electrical engineering faculty engage in interdisciplinary work.  NRC also reports that 24.62% of MIT computer science PhDs found academic employment; the actual number is twice that (49%).
• The more foreign PhD students a department had, the higher it scored.  This had the strange effect that the top departments were punished for managing to recruit more domestic students, who are the ones in much shorter supply these days.
• The complicated regression analysis used to generate the scoring formula led to the percentage of female faculty in a given department actually counting against that department’s reputation score (!).
  

Ever since the NRC data were released from the parallel universe in which they were gathered, bloggers have been having a field day with them—see for example Dave Bacon and Peter Woit, and especially Sariel Har-Peled’s Computer Science Deranker (which ranks CS departments by a combined formula, consisting of 0% the NRC scores and 100% a random permutation of departments).

Yet despite the fact that many MIT departments (for some reason not CS) took a drubbing, I actually heard some of my colleagues defend the rankings, on the following grounds:

1. A committee of good people put a lot of hard work into generating them.
2. The NRC is a prestigious body that can’t be dismissed out of hand.
3. Now that the rankings are out, everyone should just be quiet and deal with them.

But while the Forces of Doofosity usually win, my guess is that they’re going to lose this round.  Deans and department heads—and even the Computing Research Association—have been livid enough about the NRC rankings that they’ve denounced them with unusual candor, and the rankings have already been thoroughly eviscerated elsewhere on the web.

Look: if I really needed to know what (say) the best-regarded PhD programs in computer science were, I could post my question to a site like MathOverflow—and in the half hour before the question was closed for being off-topic, I’d get vastly more reliable answers than the ones the NRC took fifteen years and more than four million dollars to generate.

So the interesting questions here have nothing to do with the “rankings” themselves, and everything to do with the process and organization that produced them.  How does Charlotte Kuh, study director of the NRC’s Assessment of Research Doctorate Programs, defend the study against what now looks like overwhelming evidence of Three-Stooges-level incompetence?  How will the NRC recover from this massive embarrassment, and in what form should it continue to exist?

The NRC, as I had to look up, is an outfit jointly overseen by the National Academy of Sciences (NAS), the National Academy of Engineering (NAE), and the Institute of Medicine (IOM).  Which reminded me of the celebrated story about Richard Feynman resigning his membership in the NAS.  When asked why, Feynman explained that, when he was in high school, there was an “honor club” whose only significant activity was debating who was worthy of joining the honor club. After years in the NAS, he decided it was no different.

Now that I write that, though, an alternative explanation for the hilarious problems with the NRC study occurs to me.  The alternative theory was inspired by this striking sentence from an Inside Higher Ed article:

When one of the reporters on a telephone briefing about the rankings asked Ostriker [the chairman of the NRC project committee] and his fellow panelists if any of them would “defend the rankings,” none did so.

So, were these joke rankings an elaborate ruse by the NRC, meant to discredit the whole idea of a strict linear order on departments and universities?  If so, then I applaud the NRC for its deviousness and ingenuity in performing a much-needed public service.

Follow

Just a quick (but important) announcement: theorist-extraordinaire and friend-since-back-in-undergrad Ryan Williams reports that the Theoretical Computer Science Stack Exchange website is now up in beta!  What is this TCS Stack Exchange?  It’s a place where you can post your questions about theoretical computer science and get informed answers to them—intended as the homegrown CS theory analogue of the wildly-successful Math Overflow site.  From an initial perusal, the TCSSE looks awesome.  Indeed, the only small suggestion I can make is to propose a motto:

The TCS Stack Exchange.  Exponentially better than emailing Scott Aaronson.

Update (Sep. 10): While I’m on the topic of announcements, the early registration deadline for FOCS’2010 in Las Vegas is September 30.  Hope to see many of you there!

Another Update (Sep. 14): There’s now a beautiful talk by Ken Clarkson, Ron Fagin, and Ryan Williams looking back on the Deolalikar affair and explaining the problems with the proof, which I recommend in the strongest terms to anyone who followed this story.  (And yes, I think “looking back” is the right term here.)

Follow