Shtetl-Optimized

I thought the eight people who still read this blog might be interested to know that the FOCS’2010 Call for Papers is now out.

Firstly, if you haven’t contributed to relief efforts in Haiti, you can do so (the charity linked to was recommended by a Haitian-American working at MIT CSAIL).  I wish I had something more useful to say about this tragedy, but I don’t.

For the past couple days, I’ve been at QIP’2010 in Zurich, Switzerland.  I’d had premonitions, even before arriving, that this was going to be an unusually awesome QIP.  Having been on the PC, I knew the strength of the technical program, and I’d learned that the turnout—320 participants—would be a record high.  My positive feelings only intensified when I saw the following in the hallway of my hotel:

My buzz reached a fever pitch when I entered the lecture hall and found giant, gourmet Swiss chocolate bars on every seat.

But I only knew for sure that this QIP would rock when my erstwhile adviser, Umesh Vazirani, gave his opening plenary talk on “New bridges between computer science and quantum computation.”  Umesh highlighted several developments, including:

1. the relationship I noticed last year between the BQP versus the polynomial hierarchy problem and the Generalized Linial-Nisan Conjecture.
2. the QIP=PSPACE breakthrough of Jain et al. (based on the recent multiplicative-weights update method from classical computer science).
3. recent breakthroughs in lattice-based cryptography (most famously, Gentry’s fully homomorphic encryption system), which took inspiration from the quantum computing work of Oded Regev five years ago.
4. the work of Broadbent, Fitzsimons, and Kashefi and independently Aharonov, Ben-Or, and Eban (for which I paid out pieces of the Aaronson $25.00 Prize), which lets a “classical” verifier (equipped with the ability to send single, unentangled qubits through a channel) verify an arbitrary quantum computation; and which Umesh illustrated by a story about a verifier investigating the claims of a shady, fly-by-night company called “Q-Wave.”

Umesh argued that the deepening connections between quantum computing and classical complexity theory—open problems in classical complexity being solved using quantum-inspired techniques, tools that weren’t available in the classical world until a year or two ago already being used for quantum purposes, etc.—represent one of the most exciting new developments in the field.

The combination of the chocolate bar (which I was already eating), and Umesh preaching so much truth from the pulpit, was heavenly.

Amazingly, subsequent talks managed to keep up the momentum.  Daniel Gottesman spoke about his work with Sandy Irani on the quantum complexity of translationally-invariant tiling and Hamiltonian problems.  By giving tools to say something useful about computational complexity even in cases where the only free parameter is the system size, Gottesman and Irani open up some exciting avenues for further work.  Jordan Kerenidis spoke about the effort to prove an analogue of the Valiant-Vazirani witness isolation theorem for QMA (Quantum Merlin-Arthur).  Stefano Pironio talked about how you can exploit the Bell inequality violations to generate a long random string starting from a short random seed, assuming only the locality of the laws of physics, and not assuming anything about the reliability of your randomness-generating devices.  This observation, which I find to be of great conceptual (and conceivably even practical) interest, is related to the so-called “Free Will Theorem” of Conway and Kochen, as well as to a result I proved eight years ago in my review of Stephen Wolfram’s book.  For Conway and Kochen, though, the motivation was to prove that “subatomic particles have free will” (a strange interpretation that I don’t by any means endorse!), while for me, the motivation was to prove that Wolfram was wrong.  Neither I nor (as far as I know) Conway and Kochen thought about the obvious-in-retrospect application to generating random numbers.  (Incidentally, if anyone’s interested, my talk slides from yesterday morning are here.)

There’s also been a great deal of excitement at this year’s QIP about the efficient simulation of quantum systems occurring in nature, using recent techniques for model-order reduction (including MERA, matrix product states, quantum metropolis sampling, area laws…).  I hope I haven’t just made John Sidles faint from excitement.

The full schedule is here; feel free to ask in the comments about any talks I didn’t mention.  If there’s enough interest, I might also write a followup post about the rest of the conference.

I’m at CWI in Amsterdam, after spending two weeks in Israel.  Next week I head to QIP’2010 in Zurich, and the week after that, to the Perimeter Institute in Waterloo.

The following meta-question emerged from a conversation with Dorit Aharonov two weeks ago:

What’s your favorite example of a result in theoretical computer science that works over finite fields, but doesn’t work (or isn’t known to work) over the reals or complex numbers?

Conversely, what’s your favorite example of a result in TCS that works over the reals or complex numbers, but doesn’t work (or isn’t known to work) over finite fields?

In either case, what’s the crucial property of the underlying field, that causes the result to work in one case but not the other?

By “crucial property”, I mean something like this:

1. There’s a natural metric (i.e., a distance measure) on the reals or complex numbers, but not on a finite field.
2. There’s a uniform distribution over a finite field, but not over the reals or complex numbers.

I’d especially be interested in properties that don’t reduce to one of the two above.

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

For the female readers of this blog: I thought all eight of you might be interested in the following announcement, which was sent to me by Tal Rabin.

We will be holding the Second Women in Theory Workshop at Princeton on June 19-23, 2010.
To apply please go to: http://intractability.princeton.edu/blog/2009/11/women-in-theory-2010-workshop/
The format will be similar to the WIT 2008 workshop. You can view information on that workshop at:
http://www.cs.princeton.edu/theory/index.php/Main/WIT08
and view a video of WIT08 at: http://www.youtube.com/watch?v=uUBzBF2awZU

Several people asked me to comment on an entry by Hartmut Neven in the Google Research Blog, about using D-Wave’s “quantum” computers for image recognition.

I said nothing: what is there to say?  Didn’t I already spend enough time on this subject for 10⁴⁰⁰ lifetimes?  I want to create, explore, discover things that no one expected—not be some talking-head playing his assigned role in a script, a blogger-pundit who journalists know they can rely on to say “f(X)” whenever X happens.  Even if f(X) is true.  Why can’t I just tell the world what f is and be done with it?

Then more people asked me to comment.

I set the matter aside.  I worked on the complexity problem that’s currently obsessing me.  I met with students, sent recommendation letters, answered emails, went ice-skating with my girlfriend.

Then more people asked me to comment.

And I thought: yes, I believe it’s vital for scientists to communicate with the broader public, not just a few colleagues.  And yes, it’s important for scientists to offer a skeptical perspective on the news—since otherwise, they implicitly cede the field to those making dubious and unsubstantiated claims.  And yes, blogging is a wonderful tool for scientists to connect directly with anyone in the world who’s curious about their work.  But isn’t there some statute of limitations on a given story?  When does it end?  And why me?

Then more people asked me to comment—so I wrote the following only-slightly-fictionalized exchange.

Skeptic: Let me see if I understand correctly.  After three years, you still haven’t demonstrated two-qubit entanglement in a superconducting device (as the group at Yale appears to have done recently)?  You still haven’t explained how your “quantum computer” demos actually exploit any quantum effects?  While some of your employees are authoring or coauthoring perfectly-reasonable papers on various QC topics, those papers still bear essentially zero relation to your marketing hype?  The academic physicists working on superconducting QC—who have no interest in being scooped—still pay almost no attention to you?  So, what exactly has changed since the last ten iterations?  Why are we still talking?

D-Wave: Then you must not have read our latest press release!  Your questions are all obsolete, because now we’re recruiting thousands of volunteers over the Internet to study the power of adiabatic quantum computing!

Onlooker: Hmm, an interesting counterargument!  D-Wave might not be using quantum mechanics, but they are using the Internet!  And their new project even has a cool code-name: “AQUA@home”!  So, skeptic, how do you respond to that?

Skeptic (distractedly): You know, when I was eight years old, and dreamed of building starships and artificial intelligences in my basement, my first order of business was always to invent code-names—not just for the projects themselves, but for every little subcomponent of them.  The second order of business was to think through the marketing aspects.  What should the robot look like?  What recreational facilities should be available on the starship, and what color should it be painted?  It really, genuinely felt like I was making concrete progress toward realizing my plans.  Sure, the engine and control system still needed to be built, but at least I had code-names and “design specs”!  How many others had even gotten that far?

D-Wave: Who cares?  This isn’t some children’s game.  Keep in mind that we’re delivering a product—serving our customers, by solving the 4-by-4 Sudoku puzzles they rely on to keep their businesses running.

Skeptic: We’ve been through this how many times?  A pigeon can probably be trained to solve 4-by-4 Sudokus.  So the only relevant questions concern the details of how you solve them.  For example, how do you encode a problem instance?  How much of the work is done in the encoding procedure itself?  What evidence do you have for quantum coherence at intermediate points of the computation?  Can you measure an entanglement witness, to give people confidence that you’re doing something other than classical simulated annealing?

Onlooker: Hmm, those do seem like important questions…

D-Wave: But they’re based on outdated premises!  Today, we’re pleased to announce that, using what might be a quantum computer, and might also be a noisy, probabilistic classical computer, we can solve 5-by-5 Sudoku puzzles!

Onlooker: Whoa, awesome!  So we’re back to square one then.  As long as D-Wave’s demos only involved 4-by-4 Sudokus, the skeptic’s arguments almost had me persuaded.  But 5-by-5?  I don’t know what to think anymore.  Skeptic, where are you?  What’s your reaction to this latest development?

Skeptic: …

D-Wave: That silence you hear is the sound of the skeptic’s worldview crashing all around him!  But we haven’t even played our top card yet.  Today, we’re positively ecstatic to announce that we’ve entered into an official-sounding partnership with GOOGLE, Inc. (or anyway, with someone who works at Google Research).  Together, we’re harnessing the power of quantum adiabatic optimization to create the next generation of car-recognition systems!

Onlooker: WOW!  This debate is over, then.  I confess: D-Wave on its own did seem a bit flaky to me.  But Google is the company born without sin.  Everything they do, have done, and will ever do is perfect by definition—from building the search engine that changed the world, to running mail servers that only fail for an insignificant 0.001% of users, to keeping the Chinese people safe from lies.  And, as Google is infallible, so too its 20,000 diverse employees—who are encouraged to spend 20% of their time on high-risk, exploratory projects—have nevertheless failed to come up with a single idea that didn’t pan out.  Skeptic, show your face!  Will you admit that, through grit, moxie, old-fashioned Canadian inventiveness, and the transformative power of the Internet, D-Wave has finally achieved what the naysayers said was impossible—namely, getting someone from Google Research to coauthor a paper with them?

Skeptic: Yes.  I concede!  D-Wave wins, and I hereby retire as skeptic.  In particular, the next time D-Wave announces something, there’s no need to ask me for my reaction.  I’ll be busy tending to my own project, codenamed ARGHH@home, which consists of banging my head against a brick wall.

This will be a little experiment, in which the collaborative mathematics advocated by Timothy Gowers and others combines with my own frustration and laziness.  If it goes well, I might try it more in the future.

Let p be a complex polynomial of degree d.  Suppose that |p(z)|≤1 for all z such that |z|=1 and |z-1|≥δ (for some small δ>0).  Then what’s the best upper bound you can prove on |p(1)|?

Note: I can prove an upper bound of the form |p(1)|≤exp(δd)—indeed, that holds even if p can be a polynomial in both z and its complex conjugate (and is tight in that case).  What really interests me is whether a bound of the form |p(1)|≤exp(δ²d) is true.

Update: After I accepted Scott Morrison’s suggestion to post my problem at mathoverflow.net, the problem was solved 11 minutes later by David Speyer, using a very nice reduction to the case I’d already solved.  Maybe I should feel sheepish, but I don’t—I feel grateful.  I am now officially a fan of mathoverflow.  Go there and participate!

Anyone who feared that my taking a real job would lead to the slow demise of this blog: your fears were entirely justified.  I barely even read blogs anymore—or Twitters, or whatever the young people use nowadays.  Though come to think of it, maybe I should switch to a Twitter feed, since blogging has become too weighty and substantive for me?

In the meantime, I’ve been asked to post the following.

Simons Postdoctoral Fellowship at the Massachusetts Institute of Technology in Theoretical Computer Science

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 2010. 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 31st, 2010.

• Address to submit application: All application materials and recommendation letters should be sent electronically to theory-postdoc@csail.mit.edu.  The candidates 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 –G682
  32 Vassar Street
  Cambridge, MA 02139, USA.
  
  

The Onion has a new piece—United Airlines Exploring Viability of Stacking Them Like Cordwood—that, as usual, is grossly unrealistic.  If my own experience is any guide, the real United would never waste money on a grated floor for waste disposal, or people to shovel peanuts into a trough.

But The Onion’s exploration of the geometry of passenger-packing does raise some genuinely interesting questions.  For years, I’ve had this idea to start an airline where, instead of seats, passengers would get personal cubbyholes that were stacked on top of each other like bunk beds.  (I’d make sure the marketing materials didn’t describe them as “coffin-shaped,” though that’s what they would be.)

You could sleep in your cubbyhole—much more easily than in a seat, of course—but you could also read, watch a movie, work on your laptop, or eat (all activities that I don’t mind doing while lying down, and the first two of which I prefer to do lying down).

Besides passenger comfort, my arrangement would have at least two advantages over the standard one:

First, depending on the exact size of the cubbyholes, you could very likely fit more passengers this way, thereby lowering ticket costs.

Second, assuming the cubbyholes were ventilated, you could put little doors on them, thereby giving passengers far more privacy than in a conventional airline.  No more being immiserated by screaming babies or inane conversations, or the B.O. of the person next to you, or reading lights while you’re trying to sleep.  And, as many of you will have noticed, BQP Aarlines could provide amorous couples with a far more comfortable alternative than the bathroom.

So, readers: do you know if any airline has tried something like this?  If not, why not?  Are there strong arguments against it that I haven’t thought of, besides the obvious cultural/psychological ones?  Should I keep my day job?

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

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

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

---

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

---

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

---

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

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

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