Updates, Boolean Functions Conference, and a Surprising Application to Polytope Theory

The Debate continues

The debate between Aram Harrow and me on Godel Lost letter and P=NP (GLL) regarding quantum fault tolerance continues. The first post entitled Perpetual  motions of the 21th century featured mainly my work, with a short response by Aram. Aram posted two of his three rebuttal posts which included also short rejoiners by me. Aram’s first post entitled Flying machines of the 21th century dealt with the question “How can it be that quantum error correction is impossible while classical error correction is possible.” Aram’s  second post entitled Nature does not conspire deals with the issue of malicious correlated errors.  A third post by Aram is coming and  the discussion is quite interesting. Stay tuned. In between our posts GLL had several other related posts like Is this a quantum computer? on how to tell that you really have a genuine quantum computer , and Quantum ground day that summarized the comments to the first post.

Virgin Island Boolean Functions

In the beginning of February I spend a week in a great symposium on Analysis of Boolean Functions, one among several conferences supported  by the Simons foundation, that took place at St. John of the Virgin Islands.

Irit Dinur and me

Ryan O’Donnell who along with Elchanan Mossel and Krzysztof Oleszkiewicz (the team of “majority is stablest” theorem) organized the meeting, live blogged about it on his blog. There are also planned scribes of the lectures and videos. I posed the following problem (which arose naturally from works presented in the meeting): What can be said about circuits with n inputs representing n Gaussian random variables, and gates of the form: linear functions, max and min.

A surprising application of a theorem on convex polytopes.

(Told to me by Moritz Schmitt and Gunter Ziegler)

A theorem I proved with Peter Kleinschmidt and Gunter Meisinger asserts that every rational polytope of dimension d>8 contains a 3-face with at most 78 vertices or 78 facets. (A later theorem of Karu shows that our proof applies to all polytopes.) You would not expect to find a real life application for such a theorem. But a surprising application has just been given.

Before talking about the application let me say a few more words about the theorem. The point is that there is a finite list of 3-polytopes so that every polytope of a large enough dimension (as it turns out, eight or more) has a 3-face in the list. It is conjectured that a similar theorem holds for k-faces, and  it is also conjectured that if the dimension is sufficiently high you can reduce the list to two polytopes: the simplex and the cube. These conjectures are still open. (See this post  for related open problems about polytopes.) For k=2, it follows from Euler’s theorem that every three-dimensional polytope contains a face which is a triangle, quadrangle, or pentagon, and in dimension five and up, every polytope has a 2-face which is a triangle or a rectangle.

Continue reading

A Discussion and a Debate

Heavier than air flight of the 21 century?

The very first post on this blog entitled “Combinatorics, Mathematics, Academics, Polemics, …” asked the question “Are mathematical debates possible?” We also had posts devoted to debates and to controversies.

A few days ago, the first post in a discussion between Aram Harrow, a brilliant computer scientists and quantum information researcher (and a decorated debator), and myself on quantum error correction was launched in Dick Lipton and Ken Regan’s big-league blog, Gödel’s Lost Letter and P=NP.

The central question we would like to discuss is:

Are universal quantum computers based on quantum error correction possible.

In preparation for the public posts, Ken, Aram, Dick, and me are having very fruitful and interesting email discussion on this and related matters, and also the post itself have already led to very interesting comments. Ken is doing marvels in editing what we write.

Dick opened the post by talking on perpetual motion machines which is ingenious because it challenges both sides of the discussion. Perpetual motion turned out to be impossible: will quantum computers enjoy the same fate? On the other hand (and closer to the issue at hand), an argument against quantum mechanics based on the impossibility of perpetual motion by no other than Einstein turned out to be false, are skeptical ideas to quantum computers just as bogus? (The answer could be yes to both questions.) Some people claimed that heavier-than-air flight might is a better analogy. Sure, perhaps it is better.

But, of course, analogies with many human endeavors can be made, and for these endeavors, some went one way, and some went the other way, and for some we don’t know.

Although this event is declared as a debate, I would like to think about it as a discussion. In the time scale of such a discussion what we can hope for is to better understand each other positions, and, not less important, to better understand our own positions.  (Maybe I will comment here about some meta aspects of this developing discussion/debate.)

A real debate

A real emerging debate is if we (scientists) should boycott Elsevier. I tend to be against such an action, and especially against including refereeing papers for journals published by Elsevier as part of the boycott. I liked, generally speaking,  Gowers’s critical post on Elsevier, but the winds of war and associated rhetoric are not to my liking.  The universities are quite powerful, and they deal, negotiate and struggle with scientific publishers, and other similar bodies, on a regular  basis. I tend to think that the community of scientists should not be part of such struggles and that such involvement will harm the community and science. This is a real debate! But it looks almost over.  Many scientists joined the boycott and not many opposing opinions were made. It looks that we will have a little war and see some action. Exciting, as ever.