Shtetl-Optimized

If you’re in academia and haven’t done so yet, please take a moment to sign this online petition organized by Tyler Neylon, and pledge that you won’t publish, referee, or do editorial work for any Elsevier journals.  I’ve been boycotting Elsevier (and most other commercial journal publishers—Elsevier is merely the worst) since 2004, when I first learned about their rapacious pricing policies.  I couldn’t possibly be happier with my choice: unlike most idealistic principles, this one gets you out of onerous work rather than committing you to it!  Sure, Elsevier is huge and we’re tiny, but the fight against them is finally gathering steam (possibly because of Elseiver’s support for SOPA, PIPA, and the “Research Works Act”), years after the case against them became inarguable.  Since their entire business model depends on our donating free labor to them, all it will take to bring them down is for enough of us to decide we’re through being had.  We can actually win this one … Yes We Can.

For more information, see this wonderful recent post by Fields medalist and Shtetl-Optimized commenter Timothy Gowers, entitled “Elsevier — my part in its downfall.”  (Added: also check out this great post by Aram Harrow.)  You might also enjoy a parody piece I wrote years ago, trying to imagine how Elsevier’s “squeeze those dupes for all they’ve got” business model would work in any other industry.

Yes, I’m blogging from outside Nairobi, where I’ve come to investigate the true circumstances of President Obama’s birth.  Seriously, Dana and I are here to go on a safari for our belated honeymoon—for both of us, it’s our first non-work-related trip in many years.  Needless to say, we both brought our laptops.

Like everyone else with an ounce of sense, I’m absolutely horrified by SOPA, and inspired by the way so many Internet companies and organizations have banded together to try to prevent the United States from moving in the direction of China and Iran.

Meanwhile, on the theme of open access to information on the web, check out a New York Times article by Thomas Lin about the open science movement.  I’m quoted briefly toward the end.

Sorry for the light (nonexistent) blogging lately.  I’ll be back after I’m done with the lions and hippos and so forth.

Ho³!  Home with family for the holidays and looking for something to do?  Then check out the archives of our 6.893 Philosophy and Theoretical Computer Science course blog.  The course just ended last week, so you can find discussions of everything from the interpretation of quantum mechanics to Occam’s Razor to the Church-Turing Thesis to strong AI, as well as links to student projects, including Criticisms of the Turing Test and Why You Should Ignore (Most of) Them, Barwise Inverse Relation Principle, Bayesian Surprise, Boosting, and Other Things that Begin with the Letter B, and an interactive demonstration of interactive proofs.  Thanks to my TA Andy Drucker, and especially to the students, for making this such an interesting course.

I have a special treat for those commenters who consider me an incorrigible publicity-hound: an essay I was invited to write for the New York Times Science section, entitled Quantum Computing Promises New Insights, Not Just Supermachines.  (My original title was “The Real Reasons to Study Quantum Computing.”)  This piece is part of a collection of essays on “the future of computing,” which include one on self-driving cars by Sebastian Thrun, one on online learning by Daphne Koller, and other interesting stuff (the full list is here).

In writing my essay, the basic constraints were:

(a) I’d been given a rare opportunity to challenge at least ten popular misconceptions about quantum computing, and would kick myself for years if I didn’t hit all of them,

(b) I couldn’t presuppose the reader had heard of quantum computing, and

(c) I had 1200 words.

Satisfying these constraints was harder than it looked, and I benefited greatly from the feedback of friends and colleagues, as well as the enormously helpful Times staff.  I did get one request that floored me: namely, to remove all the material about “interference” and “amplitudes” (too technical), and replace it by something ordinary people could better relate to—like, say, a description of how a quantum computer would work by trying every possible answer in parallel.  Eventually, though, the Gray Lady and I found a compromise that everyone liked (and that actually improved the piece): namely, I’d first summarize the usual “try all answers in parallel” view, and then explain why it was wrong, bringing in the minus signs and Speaking Truth to Parallelism.

To accompany the essay, I also did a short podcast interview about quantum computing with the Times‘ David Corcoran.  (My part starts around 8:20.)  Overall, I’m happy with the interview, but be warned: when Corcoran asks me what quantum computers’ potential is, I start talking about the “try all answers in parallel” misconception—and then they cut to the next question before I get to the part about its being a misconception!  I need to get better at delivering soundbites…

One final comment: in case you’re wondering, those black spots on the Times‘ cartoon of me seem to be artifacts of whatever photo-editing software they used.  They’re not shrapnel wounds or disfiguring acne.

For weeks, I’ve been meaning to blog about an important recent paper by Stephen Jordan, Keith Lee, and John Preskill, entitled Quantum Algorithms for Quantum Field Theories.  So I’m now doing so.

As long as I’ve been in quantum computing, people have been wondering aloud about the computational power of realistic quantum field theories (for example, the Standard Model of elementary particles).  But no one seemed to have any detailed analysis of this question (if there’s something I missed, surely commenters will let me know).  The “obvious” guess would be that realistic quantum field theories should provide exactly the same computational power as “ordinary,” nonrelativistic quantum mechanics—in other words, the power of BQP (the class of problems solvable in polynomial time by a quantum computer).  That would be analogous to the situation in classical physics, where bringing in special relativity dramatically changes our understanding of space, time, matter, and energy, but seems (unlike quantum mechanics) to have little or no effect on which computational problems can be solved efficiently.  Analogously, it would seem strange if quantum field theories (QFTs)—which tie together quantum mechanics, special relativity, and detailed knowledge about the elementary particles and their interactions, but seen from far enough away are “just” quantum mechanics—forced any major revision to quantum computing theory.

Until now, though, there seems to have been only one detailed analysis supporting that conclusion, and it applied to (2+1)-dimensional topological QFTs (TQFTs) only, rather than “realistic” (3+1)-dimensional QFTs.  This was the seminal work of Freedman, Kitaev, and Wang and Freedman, Larsen, and Wang in 2000.  (Six years later, Aharonov, Jones, and Landau gave a more computer-science-friendly version, by directly proving the BQP-completeness of approximating the Jones polynomial at roots of unity.  The latter problem was known to be closely-related to simulating TQFTs, from the celebrated work of Witten and others in the 1980s.)  To a theoretical computer scientist, dropping from three to two spatial dimensions might not sound like a big deal, but what’s important is that the relevant degrees of freedom become “topological”, making possible a clean, simple model of computation.  For “realistic” QFTs, by contrast, it wasn’t even obvious how to define a model of computation; putting realistic QFTs on a rigorous mathematical footing remains a notorious open problem.

In their new paper, Jordan, Lee, and Preskill say that they give an algorithm, running on a “conventional” quantum computer, to estimate scattering probabilities in a class of QFTs called “continuum φ⁴ theories.” Their algorithm uses time polynomial in the number of incoming particles in the scattering experiment and in their total energy, and inversely polynomial in the desired precision ε and in the distance λ-λ_c between the QFT’s coupling constant λ and a phase transition λ_c.  (In d=2 spatial dimensions, they say the dependence on the precision scales like (1/ε)^2.376, the 2.376 coming from matrix multiplication. Naturally, that should now be amended to (1/ε)^2.373.)  To develop their algorithm, Jordan et al. apparently had to introduce some new techniques for coping with the error incurred by discretizing QFTs.  No classical algorithm is known with similar scaling—so when suitably formalized, the “QFT simulation problem” might indeed be in BQP-BPP, matching the uninformed doofus intuition of complexity theorists like me.  Jordan et al. don’t say whether the problem they’re solving is also BQP-complete; I imagine that could be a topic for future research.  They also don’t say whether their precision parameter ε bounds the variation distance between the real and simulated output distributions (rather than just the differences between probabilities of individual scattering outcomes); I hope they or someone else will be able to clarify that point.

In case it isn’t obvious yet, let me make it crystal-clear that I lack the physics background to evaluate Jordan et al.’s work in a serious technical way.  All I can say with confidence is that the small number of people who (1) have the requisite background and (2) care about computational complexity, will probably spend non-negligible time discussing and understanding this paper in the weeks and months to come.

Conflict-of-Interest Warning: At a deep, subconscious level, I probably chose to blog about Jordan et al.’s paper not for any legitimate scientific reason, but simply because I know John Preskill and Stephen Jordan personally, and, despite being physicists, they’re both tremendously-respected colleagues who’ve made many outstanding contributions to quantum computing theory besides this one.  Then again, everything I’ve ever done—and everything you’ve ever done—has probably had such unsavory hidden motives as well, so who’s counting?  In all of history, there have only been ten or twenty people whose commitment to scientific objectivity has been absolute and pure, and since they comment on complexity blogs anonymously, we’ll probably never even know their names…

A year ago, in a post entitled Anti-Complexitism, I tried to grapple with the strange phenomenon—one we’ve seen in force this past week—of anonymous commenters getting angry about the mere fact of announcements, on theoretical computer science blogs, of progress on longstanding open problems in theoretical computer science.  When I post something about global warming, Osama Bin Laden, or (of course) the  interpretation of quantum mechanics, I expect a groundswell of anger … but a lowering of the matrix-multiplication exponent ω?  Huh?  What was that about?

Well, in this case, some commenters were upset about attribution issues (which hopefully we can put behind us now, everyone agreeing about the importance of both Stothers’ and Vassilevska Williams’ contributions), while others honestly but mistakenly believed that a small improvement to ω isn’t a big deal (I tried to explain why they’re wrong here).  What interests me in this post is the commenters who went further, positing the existence of a powerful “clique” of complexity bloggers that’s doing something reprehensible by “hyping” progress in complexity theory, or by exceeding some quota (what, exactly?) on the use of the word “breakthrough.”

One of the sharpest responses to that paranoid worldview came (ironically) from a wonderful anonymous comment on my Anti-Complexitism post, which I recommend everyone read.  Here was my favorite paragraph:

The final criticism [by the anti-complexites] seems to be: complexity theory makes too much noise which people in other areas do not like.  I really don’t understand this one, I mean what is wrong with people in an area being excited about their area?  Is that wrong?  And where do we make those noise?  On complexity blogs!  If you don’t like complexity theorists being excited about their area why are you reading these blogs?  The metaphor would be an outsider going to a wedding and asking the people in the wedding with a very serious tone: “why is everyone happy here?”

Yesterday, in response to my reposting the above comment on Lance and Bill’s blog, another anonymous commenter had something extremely illuminating to say:

Scott, you are missing the larger socio-economical context: it’s not about excitement.  It’s about researchers competing for scarce resources, primarily funding.  The work involved in funding acquisition is generally loathed, and directly reduces the time scientists have for research and teaching.  If some researchers ramp up their hype-level vis-a-vis the rest of the community, as the complexity community is believed to be doing (what with all them Goedel awards?), they are forcing (or are seen as forcing) the rest either to accept a lower level of funding with all the concomitant disadvantages, or invest more time in hype themselves.  In other words, hypers are defecting in the prisoners dilemma type game scientists are playing, the objective of which is to minimise the labour involved in funding acquisition.

This is similar to teeth-whitening: in the past, it was perfectly possible to be considered attractive with natural, slightly yellowish teeth. Then some defected by bleaching, then more and more, and today natural teeth are socially hardly acceptable, certainly not if you want to be good-looking.  Is that progress?

I posted a response on Lance and Bill’s blog, but then decided it was important enough to repost here.  So:

Dear Anonymous 2:47,

Let me see whether I understand you correctly.  On the view you propose, other scientists shouldn’t have praised (say) Carl Sagan for getting millions of people around the world excited about science.  Rather, they should have despised him, for using hype to divert scarce funding dollars from their own fields to the fields Sagan favored (like astronomy, or Sagan’s preferred parts of astronomy).  Sagan forced all those other scientists to accept a terrible choice: either accept reduced funding, or else sink to Sagan’s level, and perform the loathed task of communicating their own excitement about their own fields to the public.

Actually, there were other scientists who drew essentially that conclusion.  As an example, Sagan was famously denied membership in the National Academy of Sciences, apparently because of a few vocal NAS members who were jealous and resentful of Sagan’s outreach activities.  The view we’re now being asked to accept is that those NAS members are the ones who emerge from the story the moral victors.

So let me thank you, Anonymous 2:47: it’s rare for anyone to explain the motivation behind angry TCS blog comments with that much candor.

Now that the real motivation has (apparently) crawled out from underneath its rock, I can examine it and refute it.  The central point is simply that science isn’t a Prisoner’s-Dilemma-type game.   What you describe as the “socially optimal equilibrium,” where no scientists need to be bothered to communicate their excitement about their fields, is not socially optimal at all—neither from the public’s standpoint nor from science’s.

At the crudest level, science funding is not a fixed-size pie.  For example, when Congress was debating the cancellation of the Superconducting Supercollider, a few physicists from other fields eagerly jumped on the anti-SSC bandwagon, hoping that the SSC money might then get diverted to their own fields.  Ultimately, of course, the SSC was cancelled, and none of the money ever found its way to other areas of physics.

So, if you see people using blogs to talk about research results that excite them, then instead of resenting it, consider starting your own blog to talk about the research results that excite YOU.  If your blog is well-written and interesting, I’ll even add you to my blogroll, game-theoretic funding considerations be damned.  Just go to WordPress.com—it’s free, and it takes only a few minutes to set one up.

Since everything I write now seems to provide an occasion for bitter controversy, I’ll be curious to learn whose sensibilities I inadvertently offended by posting the following announcement for next year’s ITCS conference. -SA

Dear Theorists:

As you know the third Innovation in Theoretical Computer Science Conference will be held in Cambridge this January:  http://research.microsoft.com/en-us/um/newengland/events/itcs2012/.

REGISTRATION IS NOW OPEN and THE PROGRAM IS ONLINE.

In addition to the program, there are going to be a few novelties that we would like to point out to you.

1. GRADUATING BITS

In one session of the conference, students graduating this academic year (as well as researchers completing their postdoc this academic year) will be given few minutes to present themselves and their work.

The presentations will be grouped by University, in alphabetic order.

We hope this will give all of us an opportunity to have a synopsis of the great work being done by the “graduating” members of our community.

In order to speak in this special session, please send an email at  silvio.itcs12@gmail.com by DECEMBER 15.

Registration fees will be waived for presenters at Graduating Bits 2012.

If you/your students are graduating this year, or you plan to hire this year, we are encourage to attend ITCS 2012!

2. COMMUNITY BUILDING

To strengthen our (legendary!) friendship and collaboration, we will treat you to a PLAY BACK show: an improvisational theater where OUR actors will bring to life YOUR stories.

3. CHAIR RANTS

In addition to the chair of each session introducing the speakers and coauthors of the session (who will then introduce themselves and their coauthors), our chairs will provide us with their insights on the papers in their sessions.

We look forward to seeing all of you in Cambridge very soon!

All the Best

Shafi Goldwasser, Silvio Micali, and Yael Tauman Kalai

For twenty years, the fastest known algorithm to multiply two n-by-n matrices, due to Coppersmith and Winograd, took a leisurely O(n^2.376) steps.   Last year, though, in his PhD thesis, Andrew Stothers gave an improvement to O(n^2.374) steps.  And today,  Virginia Vassilevska Williams of Berkeley and Stanford, released a paper that gives a general methodology for analyzing Coppersmith-Winograd-type algorithms, and that improves the matrix-multiplication time to a lightning-fast O(n^2.373) steps.  (Virgi’s work was independent of Stothers’, though she credits him and applies an idea of his to simplify her proof.)  Full disclosure: I actually knew a month ago that this was coming—I had a hell of a time keeping the secret.  I’d recommend that you get started memorizing “ω<2.373,” but as Russell Impagliazzo points out in the comments, the exponent might get lowered again in short order.  Huge congratulations to Virgi and to Andrew for this breakthrough!

Update (Nov. 30): Last night I received an extremely gracious email from Andrew Stothers, which he’s given me permission to summarize here.  In the email, Andrew expressed how excited he was about Virgi’s new result, apologized for the confusion he caused by not mentioning his improvement to ω until page 71 of his thesis (he says he doesn’t know why he did it), and said that he meant to publish a paper, but was prevented from doing so by health and job issues.  He also said that he didn’t take issue with anything I wrote here, except that I mistakenly referred to him as Andy rather than Andrew.  In response, I congratulated Andrew on his achievement; expressed how happy I was that—ironically—his work is now finally getting some of the attention that it deserves; and promised to buy him a beer when and if I’m ever in Edinburgh, a city I’ve always wanted to visit.  (On the other hand, I warned Andrew that his LinkedIn profile, which unselfconsciously mentions improvements to his Word and Excel skills as one of the benefits of his PhD research breaching the Coppersmith-Winograd barrier, might have earned him a place in scientific folklore forever!)

In summary, I now see Andrew as an extraordinarily nice fellow who had some bad luck and—most conspicuously—a lack of good advice from people around him.  I do stand by the points that I was originally trying to make:

(a) that this tangled situation shouldn’t in any way detract from Virgi’s fantastic achievement, which (except for a simplification, as she discusses) must be considered completely independent of Andrew’s, and

(b) that there’s indeed an important cautionary lesson for students here, about adequately publicizing your work (yes, there’s a happy medium, between hiring a PR firm to wage a viral marketing campaign and burying your solution to a longstanding open problem so far in the body of your PhD thesis that even world experts in the subject who read your thesis will miss it).

On the other hand, I hereby apologize for anything I said that could even be perceived as slighting Andrew, his important work, or his motives.

Another Update: On the third hand, if you’re one of the commenters whose beef is not about attribution, but about the entire concept of using a CS theory blog to “promote” major milestones in CS theory (like the breaking of the Coppersmith-Winograd barrier), then I apologize for absolutely nothing.  Go read an economics or physics blog; I understand that those are entirely hype-free.  Better yet, go to hell.

Lots of people asked me to comment on a much-discussed new preprint by Matthew Pusey, Jonathan Barrett, and Terry Rudolph (henceforth PBR), “The quantum state cannot be interpreted statistically”.  (See here for an effusive Nature News article, here for the predictable Slashdot confusion-fest, here for a related Cosmic Variance guest post by David Wallace, and here for a spiteful rant by Lubos Motl that hilariously misunderstands the new result as “anti-quantum-mechanics.”)

I recommend reading the preprint if you haven’t done so yet; it should only take an hour.  PBR’s main result reminds me a little of the No-Cloning Theorem: it’s a profound triviality, something that most people who thought about quantum mechanics already knew, but probably didn’t know they knew.  (Some people are even making comparisons to Bell’s Theorem, but to me, the PBR result lacks the same surprise factor.)

To understand the new result, the first question we should ask is, what exactly do PBR mean by a quantum state being “statistically interpretable”?  Strangely, PBR spend barely a paragraph justifying their answer to this central question—but it’s easy enough to explain what their answer is.  Basically, PBR call something “statistical” if two people, who live in the same universe but have different information, could rationally disagree about it.  (They put it differently, but I’m pretty sure that’s what they mean.)  As for what “rational” means, all we’ll need to know is that a rational person can never assign a probability of 0 to something that will actually happen.

To illustrate, suppose a coin is flipped, and you (but not I) get a tip from a reliable source that the coin probably landed heads.  Then you and I will describe the coin using different probability distributions, but neither of us will be “wrong” or “irrational”, given the information we have.

In quantum mechanics, mixed states—the most general type of state—have exactly the same observer-relative property.  That isn’t surprising, since mixed states include classical probability distributions as a special case.  As I understand it, it’s this property of mixed states, more than anything else, that’s encouraged many people (especially in and around the Perimeter Institute) to chant slogans like “quantum states are states of knowledge, not states of nature.”

By contrast, pure states—states with perfect quantum coherence—seem intuitively much more “objective.”  Concretely, suppose I describe a physical system using a pure state |ψ>, and you describe the same system using a different pure state |φ>≠|ψ>.  Then it seems obvious that at least one of us has to be flat-out wrong, our confidence misplaced!  In other words, at least one of us should’ve assigned a mixed state rather than a pure state.  The PBR result basically formalizes and confirms that intuition.

In the special case that |ψ> and |φ> are orthogonal, the conclusion is obvious: we can just measure the system in a basis containing |ψ> and |φ>.  If we see outcome |ψ> then you’re “unmasked as irrational”, while if we see outcome |φ>, then I’m unmasked as irrational.

So let’s try a slightly more interesting, non-orthogonal example.  Suppose I describe a system S using the state |0>, while you describe it using the state |+>=(|0>+|1>)/√2.  Even then, there are some measurements and outcomes of those measurements that would clearly reveal one of us to have been irrational.  If we measure S in the {|0>,|1>} basis and get outcome |1>, then I was irrational.  If we measure in the {|+>,|->} basis (where |->=(|0>-|1>)/√2) and get outcome |->, then you were irrational.  Furthermore, if S is any qubit that obeys quantum mechanics, then it must have a decent probability either of returning outcome |1> when measured in the {|0>,|1>} basis, or of returning  outcome |-> when measured in the {|+>,|->} basis.

So, are we finished?  Well, PBR don’t discuss the simple argument above, but I assume they wouldn’t be satisfied with it.  In particular, they’d probably point out that it only unmasks one of us as irrational for some measurement outcomes—but who can say what the measurement outcome will be, especially if we don’t presuppose that the quantum state provides a complete description of reality?

What they want instead is a measurement that’s guaranteed to unmask someone as irrational, regardless of its outcome.  PBR show that this can be obtained, under one further assumption: that “rational beliefs behave well under tensor products.”  More concretely, suppose two people with different knowledge could rationally describe the same physical system S using different pure states, say |0> or |+> respectively.  Then if we consider a new system T, consisting of two independent copies of S, it should be rationally possible to describe T using any of the four states |0>|0>, |0>|+>, |+>|0>, or |+>|+>.  But now, PBR point out that there’s a 2-qubit orthonormal basis where the first vector is orthogonal to |0>|0>, the second vector is orthogonal to |0>|+>, the third vector is orthogonal to |+>|0>, and the fourth vector is orthogonal to |+>|+>.  So, if we measure in that basis, then someone will get unmasked as irrational regardless of the measurement result.

More generally, given any physical system S that you and I describe using different pure states |ψ> and |φ>, PBR define a new system T consisting of k independent copies of S, where k is inversely proportional to the angle between |ψ> and |φ>.  They then construct a projective measurement M on T such that, whichever of M’s 2^k possible outcomes is observed, one of the 2^k possible “tensor product beliefs” about T gets unmasked as irrational.  And that’s it (well, other than a generalization to the noisy case).

So, will this theorem finally end the century-old debate about the “reality” of quantum states—proving, with mathematical certitude, that the “ontic” camp was right and the “epistemic” camp was wrong?  To ask this question is to answer it.

(Clarification added for Lubos Motl and anyone else unwilling or unable to understand: The answer that I intended was “no.”  I don’t think the battle between the “ontic” and “epistemic” camps can ever be won, by its nature.  Nor has that particular battle ever interested me greatly, except insofar as some interesting mathematical results have come out of it.)

I expect that PBR’s philosophical opponents are already hard at work on a rebuttal paper: “The quantum state can too be interpreted statistically”, or even “The quantum state must be interpreted statistically.”

I expect the rebuttal to say that, yes, obviously two people can’t rationally assign different pure states to the same physical system—but only a fool would’ve ever thought otherwise, and that’s not what anyone ever meant by calling quantum states “statistical”, and anyway it’s beside the point, since pure states are just a degenerate special case of the more fundamental mixed states.

I expect the rebuttal to prove a contrary theorem, using a definition of the word “statistical” that subtly differs from PBRs.  I expect the difference between the two definitions to get buried somewhere in the body of the paper.

I expect the rebuttal to get blogged and Slashdotted.  I expect the Slashdot entry to get hundreds of comments taking strong sides, not one of which will acknowledge that the entire dispute hinges on the two camps’ differing definitions.

There’s an important lesson here for mathematicians, theoretical computer scientists, and analytic philosophers.  You want the kind of public interest in your work that the physicists enjoy?  Then stop being so goddamned precise with words!   The taxpayers who fund us—those who pay attention at all, that is—want a riveting show, a grand Einsteinian dispute about what is or isn’t real.  Who wants some mathematical spoilsport telling them: “Look, it all depends what you mean by ‘real.’  If you mean, uniquely determined by the complete state of the universe, and if you’re only talking about pure states, then…”

One final remark.  In their conclusion, PBR write:

… the quantum state has the striking property of being an exponentially complicated object.  Specifically, the number of real parameters needed to specify a quantum state is exponential in the number of systems n.  This has a consequence for classical simulation of quantum systems.  If a simulation is constrained by our assumptions—that is, if it must store in memory a state for a quantum system, with independent preparations assigned uncorrelated states—then it will need an amount of memory which is exponential in the number of quantum systems.

The above statement is certainly true, but it seems to me that it was already demonstrated—and much more convincingly—by (for example) the exponential separations between randomized and quantum communication complexities.

The Theory of Computation (TOC) group at the Computer Science and Artificial Intelligence Laboratory (CSAIL) at MIT is seeking candidates for a post-doctoral position in the general area of the theory of computation. Applicants in all areas of theory are encouraged to apply, including (but not exclusive to) algorithms, complexity theory, combinatorial optimization, cryptography, distributed computing, game theory and computation, geometry, parallel computing, and quantum computing. This fellowship is made possible by a generous gift from the Simons Foundation.

The fellowship is a two year position, starting the summer or fall of 2012. The fellowship stipend is gauged to attract the highest caliber of applicants. Generous funds for scientific travel will be available for use at the fellow’s discretion. Fellows will be assigned a faculty member close to their research interests from the TOC group. Fellows will be encouraged (although not required) to teach a graduate seminar in their area of research.

Eligibility: Candidates must receive their PhD during the academic year immediately preceding that in which the fellowship would begin. There are no other restrictions based on nationality or any other basis.

Application Process: Candidate applications should include a description of professional interests and goals in research. Each application should include a curriculum vitae and the names and addresses of three or more individuals who will provide letters of recommendation. Letter writers should submit their letters directly to MIT to the address below. Please submit complete applications by January 6, 2012.

Address to submit application: All application materials and recommendation letters should be sent electronically to theory-postdoc@csail.mit.edu. The candidate’s name should be included in the subject line of the email. Alternatively, the materials can be also sent to the following address:
Simons Postdoctoral Fellowship, c/o Joanne Hanley
MIT Computer Science and Artificial Intelligence Laboratory
The Stata Center, Building 32-G672A
32 Vassar Street
Cambridge, MA 02139, USA.