Tentative Plans and Belated Updates II

 

Elementary school reunion: Usually, I don’t write about personal matters over the blog, but having (a few weeks ago) an elementary school reunion after 42 years was a moving and exciting event as to consider making an exception. For now, here is a picture:

Updates

Jirka’s Miraculous year

It looks like a lot is happening. From time to time I think that I should tell on my blog about exciting new things I hear about, but this is quite a difficult task. Perhaps I should at least post updates about progress on problems I discussed earlier, but even this is not easy.  Jirka Matousek wrote a paper entitled The dawn of an algebraic era in discrete geometry?  The paper starts as follows:

To me, 2010 looks as annus mirabilis, a miraculous year, in several areas of my mathematical interests. Below I list seven highlights and breakthroughs, mostly in discrete geometry, hoping to share some of my wonder and pleasure with the readers.

The paper lists seven startling new results. A few of these results were discussed here, a few others I have planned to discuss later, and yet a few others (like the recent solution by June Huh of the famous unimodularity conjecture for the coefficients of chromatic polynomials of graphs) caught me by a complete surprise. (Here is a link to a follow up paper by June Huh and Eric Katz.) Let me add one additional item, namely the solution (in the negative) by Boris Bukh of Eckhoff’s partition conjecture.

Other wonderful combinatorics news

These are also good times for other areas of combinatorics. I described some startling developments (e.g., here and here and here) and there is more. There were a few posts (here and here) on the Cup Set Problem. Recently Michael Bateman and Nets Katz improved, after many years, the Roth-Meshulam bound.  See these two posts on Gowers’s blog (I,II). Very general theorems discovered independently by David Conlon and Tim Gowers and by Matheas Schacht show that many theorems (such as Ramsey’s theorem or Turan’s theorem) continue to hold for substructures of sparse random sets.  Louis Esperet, Frantisek Kardos, Andrew King, Daniel Kral, and Serguei Norine proved the Lovasz-Plummer conjecture. They showed  that every cubic bridgeless graph G has at least 2^(|V(G)|/3656) perfect matchings. The concept of flag algebras, discovered by Razborov, is an extremely useful tool for extremal set theory. It has led to solutions of several problems and seems to bring us  close to a solution of  Turan’s Conjecture (which  we discussed here and here.) For example, it led to the solution by Hamed Hatami, Jan Hladký, Daniel Král, Serguei Norine, and Alexander Razborov of the question on the maximum number of pentagons in triangle-free graphs.  Hamed Hatami found a structure theorem for Boolean functions with coarse thresholds w.r.t. small probabilities. This extends and sharpens results by Ehud Friedgut and Jean Bourgain. I finally caught up (thanks to Reshef Meir) with Moser-Tardos result giving a new algorithmic proof for Lovasz local lemma. Amazing! You can read about it here.

Some updates on my Internet questions

Imre Leader and Eoin Long wrote a paper entitled tilted Sperner families, which solves a question I raised in the context of polymath1. Imre and Eoin give additional results and conjectures. My motivation was to try to come up (eventually) with very very general conjectures which include density Hales-Jewett as a very special case and are also related to error-correcting codes. Raman Sanyal discovered a dual form of Tverberg’s theorem in terms of families of fans.  (We asked about it here.) There is a new paper on the Entropy-Influence conjecture entitled The Fourier Entropy-Infuence Conjecture for certain classes of Boolean functions, by Ryan O’Donnell, John Wright, and Yuan Zhou, The paper contains a proof of the conjecture for symmetric Boolean functions and  various other cases. This is the first new result on the conjecture for many years. Also there is nice progress for the AC^0-prime number conjecture asked about in a previous post, and a subsequent Mathoverflow question (There I will keep updating matters.). Ben Green solved the conjecture! Jean Bourgain settled the more general MO question and also found results on certain AC(2) circuits.

Newton Institute and Oberwolfach,

And it seems that things are moving along nicely in other areas close to my heart.  A week ago (This was actually two months ago)  I participated in a workshop at the Newton Institute on discrete harmonic analysis. And in the first week of February we had our traditional Oberwolfach meeting on geometric and topological combinatorics. Many interesting results!

A visit to IQI

In the last week of January I visited Caltech. I missed the IPAM meeting scheduled a week before because my visa arrived too late but I still made it to IQI. This was a very nice opportunity as most of my time at Caltech was devoted to quantum information/quantum computation issues related to my own work on quantum fault tolerance. So I gave an “informal” seminar describing my point of view (and gave it again the next day at USC). Here are the slides.  My lecture was followed by two-hour discussion of the more technical details of my conjectures, seeking weak points and counterexamples in what I said, and trying to associate it with physics. There followed further discussions about some aspects of quantum fault tolerance and more general questions of quantum information with John Preskill, Leonard Schulman, Daniel Lidar and a few other people. (A lot of brilliant young people!) I learned quite a lot and was happy with this opportunity. (Of course, I did talk a little with Caltechian old and new friends about bona fide combinatorics questions.)

Three jokes for a dollar

On the weekend I took the LA metro (whose mere existence surprised me) and visited downtown LA and Hollywood. Next to Pershing station a person stopped me and asked if I want to buy three jokes for one dollar. I first said no, but then I reconsidered, called him back and gave him a dollar. To his disappointment and mine I did not understand the first joke, but the other two (perhaps adjusted to my revealed level of understanding) were quite good.

Hectic semester at HUJI

Here at Huji things are as hectic as always with 10-15 weekly research seminars. This week (This was two months ago; the semester have just ended). Continue reading

Aaronson and Arkhipov’s Result on Hierarchy Collapse

hc

Scott Aaronson gave a thought-provoking lecture in our Theory seminar three weeks ago.  (Actually, this was eleven months ago.) The slides are here . The lecture discussed two results regarding the computational power of quantum computers. One result from this paper gives an oracle-evidence that there are problems in BQP outside the polynomial hierarchy.  The method is based on “magnification” of results on bounded depth circuits. (It is related to the Linial-Nisan conjecture.)

The second result that we are going to discuss in this post (along with some of my provoked thoughts) is a recent result of Scott Aaronson and Alex Arkhipov which asserts that if  the power of quantum computers can be simulated by digital computers  then the polynomial hierarchy collapses.  More precisely, their result asserts that if sampling  probability distribution created by quantum computers (this is abbreviated as QSAMPLE) is in P then the polynomial hieararchy collapses to its third level.

The beautiful and important paper of Aaronson and Arkhipov is now out. Its main point of view is related to what I describe in the sixth section about “photon machines”. Update: Let me mention related idependent results by Michael J. Bremner, Richard Jozsa, Dan J. Shepherd in the paper entitled: “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy“.

Here is the plan for this post

1) The polynomial hierarchy and results about hierarchy collapse

2) The Aaronson Arkhipov (AA) theorem and its proof

3) Two problems posed by AA

Those are: does P=BQP already leads to a collapse of the polynomial hierarchy? And does APPROXIMATE-QSAMPLE already leads to a collapse?

4) Does fault tolerance allow QSAMPLE (on the nose)? (Answer: yes)

5) Is there a quantum analog to Aaronson and Arkhipov’s result and what is the computational power of quantum computers?

6) Three Two competing scenarios

7) Aaronson and Arkhipov photon machines and the complexity class BOSONSAMPLING.

Continue reading