Tag Archives: Updates



Ilya Rips and me during Ilyafest last week (picture Itai Benjamini)

Ilya Rips Birthday Conference

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!

2.10.14 Geometric & Combinatorial poster

Achimedes on infinity

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.


The combinatorics school (midrasha) is coming.

17.8.14 midrasha poster 2015

Two weeks with extensive illuminating lecture series. Do not miss!

At Combsem

On our Monday combinatorics seminar, we had, since my last report,  three excellent lectures. And next  Monday we are having Avi Wigderson.

Dec 1

Speaker: Sonia Balagopalan, HU

Title: A 16-vertex triangulation of the 4-dimensional real projective space 

Continue reading

Pictures from Recent Quantum Months


A special slide I prepared for my lecture at Gdansk featuring Robert Alicki and I as climber on the mountain of quantum computers “because it is not there.”

It has been quite a while since I posted here about quantum computers. Quite a lot happened in the last months regarding this side of my work, and let me devote this post mainly to pictures. So here is a short summary going chronologically backward in time. Last week – Michel Dyakonov visited Jerusalem, and gave here the condensed matter physics seminar on the spin Hall effect. A couple of weeks before in early January we had the very successful Jerusalem physics winter school on Frontier in quantum information. (Here are the recorded lectures.) Last year I gave my evolving-over-time lecture on why quantum computers cannot work in various place and different formats in Beer-Sheva, Seattle, Berkeley, Davis (CA), Gdansk, Paris, Cambridge (US), New-York, and Jerusalem. (The post about the lecture at MIT have led to a long and very interesting discussion mainly with Peter Shor and Aram Harrow.) In August I visited Robert Alicki, the other active QC-skeptic, in Gdansk and last June I took part in organizing a (successful) quantum information conference Qstart in Jerusalem (Here are the recorded lectures.).

And now some pictures in random ordering

2013-08-01 10.09.28

With Robert Alicki in Gdynia near Gdansk


With (from left) Connie Sidles, Yuri Gurevich, John Sidles and Rico Picone in Seattle  (Victor Klee used to take me to the very same restaurant when I visited Seattle in the 90s and 00s.) Update: Here is a very interesting post on GLL entitled “seeing atoms” on John Sidles work.


With Michel Dyakonov (Jerusalem, a few days ago)


With Michal Horodecki in Sopot  near Gdansk (Michal was a main lecturer in our physics school a few weeks ago.)


Aram Harrow and me meeting a year ago at MIT.

2013-08-01 10.12.45

2013-08-01 10.12.52

Sometimes Robert and I look skeptically in the same direction and other times we look skeptically in opposite directions. These pictures are genuine! Our skeptical face impressions are not staged. The pictures were taken by Maria, Robert’s wife. Robert and I are working for many years (Robert since 2000 and I since 2005) in trying to examine skeptically the feasibility of quantum fault-tolerance. Various progress in experimental quantum error-correction and other experimental works give good reasons to believe that our views could be examined in the rather near future.


A slide I prepared for a 5-minute talk at the QSTART rump session referring to the impossibility of quantum fault-tolerance as a mild earthquake with wide impact.

GTprod2This is a frame from the end-of-shooting of a videotaped lecture on “Why quantum computers cannot work” at the Simons Institute for the Theory of Computing at Berkeley. Producing a videotaped lecture is a very interesting experience! Tselil Schramm (in the picture holding spacial sets of constant width) helped me with this production.

Meeting with Aram Harrow, and my Lecture on Why Quantum Computers Cannot Work.

Last Friday, I gave a lecture at the quantum information seminar at MIT entitled “Why quantum computers cannot work and how.” It was a nice event with lovely participation during the talk, and a continued discussion after it. Many very interesting and useful remarks were made. Here are the slides. (The abstract can be found on this page.)

After having an almost a yearlong debate with Aram Harrow, I finally met Aram in person, and we had nice time together during my visit.


Aram is so nice that had it been up to me I would certainly make quantum computers possible :) (But this is not up to us and all we can do is to try to explore if QC are possible or not.)

We talked about quite a few topics starting with various exotic models of noise that treat differently classic and quantum information, the relevance of locally correctable codes and their quantum counterparts, the sum of Squares/Lasserre hierarchy, unique games and hypercontractivity, my smoothed Lindblad evolutions , NMR and spin-echo, quantum annealing and stoquasicity, and works by Mossbüer, Rekha Thomas, and Monique Laurent were mentioned. 


I just returned yesterday night from Yale after a very fruitful visit.  Here is a picture of a snowcar decorated with car mirrors from the great blizzard.

winter12 224

Plans and Updates

Jerusalem and Budapest




Monday, last week was the last day of lectures for the spring term here at the Hebrew U.  One outcome of the long professors’ strike was a very fruitful year for research seminars. We ran them during the strike and we run when we taught. I heard about quite a lot of nice developments recently. Zeev Dvir gave a talk on the finite field Kakeya problem. The proof was extremely simple to start with (see Tao’s post ) and Zeev’s presentation was even simpler. It is a very interesting question how, given Dvir’s proof, we should now view the connection between the finite field version of the problem and the original problem. Does Dvir’s proof support the possibility that the original problem is not as hard as feared? Does it support the view that the finite case is not related to the continuous case? (Both Tao and Laba discuss these questions.)

I will tell you in very rough terms (which represent my partial understanding of the matter) one recent wonderful development I heard about.  Kolmogorov and Sinai proved that the Entropy is an invariant for Bernoulli shifts under isomorphism.  Ornstein celebrated isomorphism theorem  asserts that entropy is the only invariant. Orenstein and Weiss studied other group actions, and extended these theorems to amenable groups. There were strong indications that free-group actions behave very differently. (There were examples where the entropy function went the wrong way for “factors”.) However, Lewis Bowen has just shown that for free-group action entropy is an invariant! (OK, I oversimplified matters here for the sake of telling the story.) And he further proved a similar result for all “sofic groups”, a strange notion of groups which is a mixture of amenable and residually finite groups that, as far as we know, may include all groups. Benji Weiss told us about it in the “basic notions seminar”, and a few weeks later another lecture was given by the man himself – Lewis Bowen – who came from Hawaii for a short visit.

And last week I participated in a meeting “Building Bridges” in Budapest honoring Laci Lovász for his birthday. A lot of interesting talks on extremal combinatorics, graph theory, optimization, probabilistic combinatorics, and theoretical computer science. I will come back to this meeting later but let me mention one talk which I found very surprising: Peter Winkler talked about his work with Rick Kenyon on branched polymers. Kenyon and Winkler found startling simple combinatorial proofs to starling results of Brydges and Imbrie, and proved further results. I hope to add a link to the actual presentation. Hungary is the discrete mathematics superpower and on top of that as Einat Wigderson recently made clear “The Hungarians are also much funnier”.  It was nice to meet many old friends (and annoy them, at times, with silly jokes). Here is Micky Simonovits and here you can see Endre Szemeredi, Anna Szemeredi, Szemeredi’s jacket and Szemeredi’s tie. I followed the name of the conference and talked about mathematics of social choice.




We had a few slow weeks on the blog and as the saying goes: “If you cannot do, plan, and if you cannot plan, plan plans.” Together with a little summary of previous posts, I will describe some of the things I plan to write next on this blog.

I plan five posts in the series about Extremal combinatorics. Part I was an introduction to the subject and dealt with extremal set theory. Part II was about simple extremal problems in plane geometry and additive number theory, and about difficult theorems which became quite easy in time. Extremal Combinatorics III will present several basic results in extremal set theory; Part IV will be about POSETS, and part V will present the Frankl-Wilson theorem, or, at least, special cases.

I gave four posts (I, II, III, IV) based on my lecture in Marburg, dealing with high dimensional Cayley formula. Richard Stanley gave a detailed remark on why the fantasy about weighted correct version of MacMahon’s conjecture for solid partitions is not what standard proofs of the plane partition case extend to. I plan a little series of posts on “f-vectors and homology,” which was the title of a paper with Bjorner in 1988 as well as of my talk in Stockholm.  However, before that I want to describe the “g-conjecture for spheres” a central problem in algebraic combinaorics.

We had several posts on convex polytopes.  I next plan to discuss the diameter problem for polytopal graphs (the Hirsch conjecture) and related questions on the simplex algorithm. (In fact, we already started.) The one proof I presented most often in lectures is my proof of the Blind-Mani theorem that asserts that simple polytopes are determined by their graphs. I will try to blog this proof, tell you some open problems around it, and write about a startling theorem of Eric Friedman who found a polynomial-time algorithm. I also updated the post on five open problems regarding convex polytopes and added two additional problems.

We talked about influence but not about a major technique which emerged in their study: Fourier Analysis of Boolean functions.” So we will discuss Boolean functions and their spectrum, and revisit influences and look at noise-sensitivity. Muli Safra will give a post on the Goldreich Levin theorem and related stuff.

So far our open discussion “Is mathematics a science” attracted a single (nice) comment, and the poem translation contest is still waiting for quality translations. Perhaps we can try an open discussion of a single theorem/problem and see how it goes. Meanwhile, have a look at the very successful discussion on Secret Blogging Seminar about the shy and secretive mathematicians, and how they triumph again and again.

Let’s talk some more on economics and rationality. And about sociel welfare functions and voting methods. We discussed some controversies related to rationality in this post, and the Notices book-review about economics and common sense supplied a source for two posts (1,2).  I was just told that along with Landsburg’s book itself, my book review might be translated to Arabic. Sababa!

I will tell you about my ideas regarding detrimental noise for quantum computations, but only after trying to describe something about the beautiful, deep, and surprising subject of quantum computation and quantum information. I will not do it before having at least one post about classical computation complexity. Meanwhile, let me link you to the classical post by Aaronson “Reasons to believe” (on why we believe that NP is not P). And while at it, look at “Reason to believe II” (on why many of us believe that quantum computers are feasible.) Read also Bernard Chazelle’s thoughts about alorithms and science.

The most successful link we had so far was  Continue reading

Tel-Aviv’s “Jerusalem Beach”


Friday’s evening at the beach

Late Friday afternoon, and the “Jerusalem beach” in Tel Aviv is still quite crowded with young and old people, families and singles, tourists, foreign workers and Israelis. The sea is calm and beautiful and the Tel Aviv shore landscape of people and buildings is restless and captivating. A young Philippine man with a baby on his shoulders ends a long cell phone conversation spoken in a strange language, with the familiar Hebrew ending “yalla bye“. A  father of a Russian speaking family takes pictures of his family with his cell phone, as does the father of an Arabic speaking family on our other side; in fact people all over the place are taking  pictures of each other with their cell phone cameras. What do they do with all these pictures? Where do they store them?

On our other side, another groups of foreign workes, six young women and two men. Two try to play beach paddle ball (matkot), a national Israeli beach game. They also take cell phone pictures, and then one plays the guitar and they all sing, “Jesus is our savior”, and “Jesus is our Shephard”, and even one song in Hebrew.

The sunset is breathtaking. A long waiting and then when the time comes the big orange sun disappears in a matter of seconds. Many people take sunset pictures with their cell phones.

On the way back we see three nuns with black outfits and one priest. They have serious expressions. They are Greek Orthodox, I think. The priest spins his hat in the air and tries to catch the hat with his head.     




I have uploaded to the archive a paper on noisy quantum computation, which is a revision and an extension of my paper from 2006. A paper of Ehud Friedgut, Noam Nisan and myself about manipulations in voting rules was accepted to FOCS08. This is my 4th FOCS/STOC paper. (Larry Stockmeyer was a coauthor in one of my papers.)  I am planning to blog on issues around these two papers sometime in the future. (Meanwhile, there is an interesting post and discussion on quantum computers skepticism on Scott Aaronson’s blog.) Remember A. Nilli? We danced in her wedding on Sunday! Congratulations Nilli and John! As this post is launched I am at a high-dimensional phenomena conference in Sevillia. I have updated (or will soon update) the post about Han’s formula and provided more details. I also added a link to an interesting discussion on “Secret Blogging Seminar” related to my post “Is mathematics a Science”.

Continue reading