With Ilan, my four month old grandson
A quick schematic road-map to these new geometric objects. The positroidron can be seen as a cellular structure on the nonnegative Grassmanian – the part of the real Grassmanian G(m,n) which corresponds to m by n matrices with all m by m minors non-negative. The cells in the cellular structure of the positroidron correspond to those matrices with the same (+,0) pattern for m by m minors. When m=1 we get a (spherical) simplex. When we project the positroidron using an n by k totally positive matrix we get for m=1 the cyclic polytope, and for general m the amplituhedron. When we project using general matrices we obtain general polytopes for m=1, and an interesting extension of polytopes proposed by Thomas Lam for general m.
Alex Postnikov’s recent lectures series in our Midrasha was an opportunity to understand slightly better some remarkable combinatorial objects that drew much attention recently. Continue reading
The topological Tverberg conjecture (discussed in this post), a holy grail of topological combinatorics, was refuted! The three-page paper “Counterexamples to the topological Tverberg conjecture” by Florian Frick gives a brilliant proof that the conjecture is false.
The proof is based on two major ingredients. The first is a recent major theory by Issak Mabillard and Uli Wagner which extends fundamental theorems from classical obstruction theory for embeddability to an obstruction theory for r-fold intersection of disjoint faces in maps from simplicial complexes to Euclidean spaces. An extended abstract of this work is Eliminating Tverberg points, I. An analogue of the Whitney trick. The second is a result by Murad Özaydin’s from his 1987 paper Equivariant maps for the symmetric group, which showed that for the non prime-power case the topological obstruction vanishes.
It was commonly believed that the topological Tverberg conjecture is correct. However, one of the motivations of Mabillard and Wagner for studying elimination of higher order intersection was that this may lead to counterexamples via Özaydin result. Isaak and Uli came close but there was a crucial assumption of large codimension in their theory, which seemed to avoid applying the new theory to this case. It turned out that a simple combinatorial argument allows to overcome the codimension problem!
Florian’s combinatorial argument which allows to use Özaydin’s result in Mabillard-Wagner’s theory is a beautiful example of a powerful combinatorial method with other applications by Pavle Blagojević, Florian Frick and Günter Ziegler.
Both Uli and Florian talked about it here at Oberwolfach on Tuesday. I hope to share some more news items from Oberwolfach and from last week’s Midrasha in future posts.
Update (May, 2016): The combinatorial method of Blagojević, Frick and Ziegler was earlier and independently discovered by Gromov.
Update 3 (January 30): The midrasha ended today. Update 2 (January 28): additional videos are linked; Update 1 (January 23): Today we end the first week of the school. David Streurer and Peter Keevash completed their series of lectures and Alex Postnikov started his series.
Today is the third day of our winter school. In this page I will gradually give links to to various lectures and background materials. I am going to update the page through the two weeks of the Midrasha. Here is the web page of the midrasha, and here is the program. I will also present the posters for those who want me to: simply take a picture (or more than one) of the poster and send me. And also – links to additional materials, pictures, or anything else: just email me, or add a comment to this post.
Michel Dyakonov’s View on QC My view (based on Michel’s drawing*)
Alexander Vlasov’s view (based on Michel and Konstantin’s drawing)
It has been a while since I devoted a post to quantum computation. Meanwhile, we had a cozy, almost private, easy-going, and very interesting discussion thread on my previous, March 2014 post (that featured my Simons Institute videotaped lectures (I,II).)
Last week we had a workshop on “Quantum computing: achievable reality or unrealistic dream.” This was a joint venture of the American Physics Society and the Racah Institute of Physics here at HUJI, organized by Professor Miron Ya. Amusia, and it featured me and Nadav Katz as the main speakers. Here are the slides of my lecture: What can we learn from a failure of quantum computers.
Earlier, I gave a lecture in our CS colloquium about a recent work with Guy Kindler on noise sensitivity of BosonSampling. We show that for a constant level of noise, noisy BosonSampling can be approximated by bounded-depth computation, and that the correlation between the noisy outcome and the noiseless outcome tends to zero if the noise level is ω(1/n) where n is the number of bosons. Here is the paper Gaussian noise sensitivity and BosonSampling, the videotaped lecture Complexity and sensitivity of noisy BosonSampling, and the slides of the lecture.
On the positive side, Greg Kuperberg and I wrote a paper Contagious error sources would need time travel to prevent quantum computation showing that for a large class of correlated noise, (teleportation-based) quantum fault-tolerance works! Greg and I have had a decade-long email discussion (over 2000 emails) regarding quantum computers, and this work grew from our 2009 discussion (about my “smoothed Lindblad evolution” model), and heavily relies on ideas of Manny Knill.
Some years ago, two brilliant experimentalists, Hagai Eisenberg and Nadav Katz, joined the already strong, mainly theoretical, quantum information group here at HUJI. Nadav Katz gave the second lecture in the workshop, and here are the slides of Nadav’s lecture: Quantum information science – the state of the art.
Also very much on the positive side, Nadav mentioned a remarkable recent progress by the Martini’s group showing certain encoded states based on 9 physical qubits which are order-of-magnitude (factor 8.4, to be precise,) more stable than the “raw” qubits used for creating them !!
Here is a link to the paper: State preservation by repetitive error detection in a superconducting quantum circuit, by J. Kelly, R. Barends, A. G. Fowler, A. Megrant, E. Jeffrey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Yu Chen, Z. Chen, B. Chiaro, A. Dunsworth, I.-C. Hoi, C. Neill, P. J. J. O’Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, A. N. Cleland, and John M. Martinis.
Update: Further comments on a Shtetl-optimized post (especially a comment by Graeme Smith,) help to place the new achievement of the Martinis group within the seven smilestones toward quantum computers from a 2012 Science paper by Schoelkopf and Devoret, originated by David DiVincenzo’s 2000 paper “The physical implementation of quantum computation“. (You can watch these milestone here also .)
The new achievement of having a very robust realization of certain encoded states can be seen as achieving the 3.5 milestone. The difference between the 3.5th milestone and the 4th milestone plays a central role in the seventh post of my 2012-debate with Aram Harrow in connection with a conjecture I made in the first post (“Conjecture 1″). Aram made the point that classical error-correction can lead to very stable encoded qubits in certain states (which is essentially the 3.5 milestone). I gave a formal description of the conjecture, which essentially asserts that the 4th milestone, namely insisting that encoded qubits allows arbitrary superpositions, cannot be reached. As I said many times (see, for example, the discussion in my 2012 Simons Institute videotaped lecture 2), a convincing demonstration of the 4th milestone, namely implementation of quantum error-correction with encoded qubits which are substantially more stable than the raw qubits (and allow arbitrary superposition for the encoded qubit) will disprove my conjectures. Such stable encoded qubits are expected from implementations of distance-5 surface code. So we are 0.5 milestones away
I will be impressed to see even a realization of distance-3 (or distance-5) surface code that will give good quality encoded qubits, even if the encoded qubits will have a quality which is somewhat worse than that of the raw qubits used for the encoding. These experiments, including those that were already carried out, also give various other opportunities to test my conjectures.
My lecture on predictions from the failure of QC is based on two lengthy recent comments (first, second) regarding predictions from the failure of quantum computers. On April 2014, Peter Shor challenged me with the following: Continue reading
Last week I took a bus from Tel Aviv to Jerusalem and I saw (from behind) a person that I immediately recognized. It was Nimrod Megiddo, from IBM Almaden, one of the very first to relate game theory with complexity theory, one of the pioneers of computational geometry, and one of the leaders in optimization and linear programming, the guy who (with Ehud Kalai) was the first to invited me to an international conference, and a fresh Laureate of the John von Neumann theory Prize. I did not see Nimrod more than a year after our last coincidental meeting at the Berkeley Simons Institute, I called over to him and he was happy to see me as I was happy to see him, and we found a place together at the back of the bus and caught up on things.
Nimrod showed me on the bus a picture he found in his house, taken by him at the 1974 game theory workshop in Bad Salzuflen, Germany. With Nimrod’s kind permission I present the picture here: (The copyright © belongs to Nimrod Megiddo who took the picture).
Here are some of the people left to right, (on some I already told you in other posts):
David Schmeidler (only beard visible)
Yair Tauman (only back shown)
Werner Güth (behind Aumann)
Ehud Kalai (just to the right of Selten looking at the camera)
Elon Kohlberg (only back shown, looking to the left)
William Lucas (in the back, looking at the wall)
Robert Weber (only hair and jacket visible)
Bezalel Peleg (looking to the right)
Joel Moulen (looking to the left)
Thomas Marschak (sunglasses and beard)
Joachim Rosenmüller (with glasses behind Maschler)
Happy new 2015!
Scott Aaronson wrote a new post on the Shtetl Optimized** reflecting on the previous thread (that I referred to in my post on Amy’s triumph), and on reactions to this thread. The highlight is a list of nine of Scott’s core beliefs. This is a remarkable document and I urge everybody to read it. Yes, Scott’s core beliefs come across as feminist! Let me quote one of them.
7. I believe that no one should be ashamed of inborn sexual desires: not straight men, not straight women, not gays, not lesbians, not even pedophiles (though in the last case, there might really be no moral solution other than a lifetime of unfulfilled longing). Indeed, I’ve always felt a special kinship with gays and lesbians, precisely because the sense of having to hide from the world, of being hissed at for a sexual makeup that you never chose, is one that I can relate to on a visceral level. This is one reason why I’ve staunchly supported gay marriage since adolescence, when it was still radical. It’s also why the tragedy of Alan Turing, of his court-ordered chemical castration and subsequent suicide, was one of the formative influences of my life.
In the sacred tradition of arguing with Scott I raised some issues with #5 and 4# on Scott’s blog. Two of Scott’s points are on the subject of (young) people’s suffering by feeling unwanted, sexually invisible, or ashamed to express their desires.
I was pleased to see that those feminist matters that Scott and I disagree about, like the nature of prostitution, the role of feminist views in men’s (or nerdy men’s) suffering, and also Scott’s take on poverty, did not make it to Scott’s core beliefs.
Happy new year, everybody!
* The word triumph is used here (again) in a soft (non-macho) way characteristic to the successes of feminism. Voting rights for women did not exclude voting rights for men, and Scott’s triumph does not mean a defeat for any others; on the contrary.
** “Shtetl-optimized” is the name of Scott Aaronson’s blog.
*** In my opinion, when a person has an uncontrollable urge or strong temptation or desire to commit a crime towards another individual (or even to inflict much damage on another person when it is not criminal, or to commit other crimes), shame and guilt feelings can be instrumental in controlling such urges.
It was not until the 144th comment by a participants named Amy on Scott’s Aaronson recent Shtetl-optimized** post devoted to a certain case of sexual harassment at M. I. T. that the discussion turned into something quite special. Amy’s great comment respectfully disagreeing with the original post and most of the 100+ earlier comments gave a wide while personal feminist perspective on women in STEM (STEM stands for science, technology, engineering, mathematics). This followed by a moving comment #171 by Scott describing a decade of suffering from his early teens. Scott, while largely sympathetic with the feminist cause, sees certain aspects of modern feminism as major contributors to his ordeal.
Then came a few hundred comments by quite a few participants on a large number of issues including romantic/sexual relations in universities, rape, prostitution, poverty, gaps between individuals’ morality and actions, and much more. Many of the comments argued with Amy and a few even attacked her. Some comments supported Amy and some proposed their own views. Many of the comments were good and thoughtful and many gave interesting food for thought. Some people described interesting personal matters. As both Scott and Amy left school early to study in the university, I also contributed my own personal story about it (and Scott even criticized my teenage approach to life! ). Amy, over 80+ thoughtful comments, responded in detail, and her (moderate) feminist attitude (as well as Amy herself) stood out as realistic, humane, and terribly smart.
* The word triumph is used here in a soft (non-macho) way characteristic to the successes of feminism. Voting rights for women did not exclude voting rights for men, and Amy’s triumph does not mean a defeat for any others; on the contrary.
** “Shtetl-optimized” is the name of Scott Aaronson’s blog.
Ilya Rips and me during Ilyafest last week (picture Itai Benjamini)
Last week we had here a celebration for Ilya Rips’ birthday. Ilya is an extraordinary mathematician with immense influence on algebra and topology. There were several startling ongoing mathematical projects that he is involved with that were discussed. One is a very ambitious project with Alexei Kanel-Belov is to get a “small cancellation theory” for rings and this has already fantastic consequences. Another is a work with Yoav Segev and Katrin Tent, on sharply 2- transitive groups, that answered a major old question with connections to groups, rings, and geometry. Happy birthday, Ilya!
Reviel Netz (רויאל נץ) gave a seminar lecture in the department about infinity in Archimedes’ mathematical thoughts that developed into an interesting conversation. The lecture took place a day after Netz’s second poetry book (in Hebrew) appeared.
Two weeks with extensive illuminating lecture series. Do not miss!
On our Monday combinatorics seminar, we had, since my last report, three excellent lectures. And next Monday we are having Avi Wigderson.
Speaker: Sonia Balagopalan, HU
Title: A 16-vertex triangulation of the 4-dimensional real projective space
When can we properly color the vertices of a graph with a few colors? This is a notoriously difficult problem. Things get a little better if we consider simultaneously a graph together with all its induced subgraphs. Recall that an induced subgraph of a graph G is a subgraph formed by a subset of the vertices of G together with all edges of G spanned on these vertices. An induced cycle of length larger than three is called a hole, and an induced subgraph which is a complement of a cycle of length larger than 3 is called an anti-hole. As usual, is the chromatic number of G and is the clique number of G (the maximum number of vertices that form a complete subgraph. Clearly, for every graph G
Question 1: Describe the class of graphs closed under induced subgraphs, with the property that for every .
A graph G is called perfect if for every induced subgraph H of G. So Question 1 asks for a description of perfect graphs. The study of perfect graphs is among the most important areas of graph theory, and much progress was made along the years.
Interval graphs, chordal graphs, comparability graphs of POSETS , … are perfect.
Two major theorems about perfect graphs, both conjectured by Claude Berge are:
The perfect graph theorem (Lovasz, 1972): The complement of a perfect graph is perfect
The strong perfect graph theorem (Chudnovsky, Robertson, Seymour and Thomas, 2002): A graph is perfect if and only if it does not contain an odd hole and an odd anti-hole.
There are triangle-free graphs with arbitrary large chromatic numbers. An important construction by Mycielski goes as follows: Given a triangle graph G with n vertices create a new graph G’ as follows: add n new vertices and a vertex w. Now add w to each and for every i and j for which and are adjacent add also an edge between and (and thus also between and .)
Question 2: Describe classes of graphs closed under induced subgraphs with bounded chromatic numbers.
Here are three theorems in this direction. The first answers affirmatively a conjecture by Kalai and Meshulam. The second and third prove conjectures by Gyarfas.
The Trinity graph theorem (Bonamy, Charbit and Thomasse, 2013): Graphs without induced cycles of length divisible by three have bounded chromatic numbers.
(The paper: Graphs with large chromatic number induce 3k-cycles.)
Theorem (Scott and Seymour, 2014): Triangle-free graphs without odd induced cycles have bounded chromatic number.
(The paper: Coloring graphs with no odd holes.)