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.
The proof was used in art! By artist Bernard Venet. If you click on his name you will reach his very beautiful site, and among other things, you will find there, under the category painting and the subcategory equation paintings, that the fourth painting is based on our proof.
A piece of Venet’s painting
Another St John picture
Combinatorics and more 