Avi Wigderson gave a great CS colloquium talk at HUJI on Monday (a real auditorium talk with an audience of about 200 people). The title of the talk was

The Value of Errors in Proofs – a fascinating journey from Turing’s 1936 seminal R ≠ RE to the 2020 breakthrough of MIP* = RE

A large part of the talk was devoted to the series of conceptually new forms of proofs compared to the ordinary notion of proofs in mathematics. Starting from the 1980s, these new notions of proofs came from theoretical computer science. They include Zero-knowledge proof (ZKP), interactive proofs (IP), multi-prover interactive proofs (MIP), probabilistically checkable proofs (PCP), and the very recent quantum multi prover interactive proofs. Of course, all these proofs are probabilistic; the prover convinces the verifier(s) that a mathematical statement is correct only with very high probability.

One little disagreement Avi and I have is whether the probabilistic proofs of mathematical statements (from the 70s) could be regarded as a major new type of mathematical proof coming from TCS. For example, in connection with the efficient primality testing of Solovay-Strassen and Rabin-Miller, Rabin’s paper stated the following theorem:

is a prime!

At that time, this theorem had only a probabilistic proof: you can be convinced that the statement is correct with very high probability depending on some internal randomization. I remember hearing a lecture by Rabin about it in the mid 70s where he was happy about this new notion of a proof (2000 years after Euclid) for a mathematical theorem. (And I was also happy about it.)

OK, now for the disagreement: in my view, Rabin’s proof that is a prime (and similar results), is indeed a new startling notion of mathematical proof coming from TCS that belongs to this series of later discoveries and could even be regarded as one of its starting points.

According to Avi, Rabin’s proof that is a prime is, in fact, not a proof at all! The ordinary notion of mathematical proof is captured by the class NP, and proofs are not relevant at all for statements that can be verified by efficient algorithms (whether deterministic or randomized).

This debate is 30% semantic, and 10% a matter of historical assessment and giving proper credits, but I think it is 50% a serious question about the interface of insights from theoretical computer science and practical reality, and of interpretation of results from TCS. In this case, it is about the meaning of proofs in mathematics and the practice of proving mathematical theorems.

What do you think?

(Of course, of an even greater importance is the interface between insights from TCS and the practical reality of computation.)

To cheer you up even further a new story that breaks new ground about Avi Wigderson and me (and Laci Lovasz) and a couple more famous Isrealis. For another story about Avi and me see Layish. (I told both stories last Friday in a party for Avi.)

It was a good time to have dinner together with Avi. Avi and I came back to Israel after Laci Lovasz’s birthday conference, “LL70 Building Bridges II”. While there, I gave a talk titled “Demolishing bridges and building new ones” and a provocative remark I made on TCS and computational reality led to an exchange of remarks, first during the lecture itself, later at our Budapest hotel, and in the following couple of weeks it developed into an untypical heated email discussion between us. It was good to put this debate behind us, and the Suzanna restaurant in Neve Tzedek was the perfect place to relax. It is a lovely place and as we were chatting about all sorts of things, Avi noticed and drew our attention to a very famous Israeli in one of the nearby tables.

After decades of collaboration between Avi and me (on silly things) we did not need to talk much and acted like a well-oiled machine. “There is a problem” I told the waiter and Avi continued: “Having Uri Geller sitting here is dangerous, if some forks bend this may cause injuries to the tongues and upper palates of of the diners.” and I added “You better find a separate room for Uri Geller and his party,” and Avi continued “fully covered with lead might be an advantage”. The waiter did not know what to say and called a colleague and we continued to discuss this matter with them.

Uri Geller, who overheard the discussion, came over to the table and asked what all the fuss was about. We explained slowly and carefully the dangers of having him sit in the next table. “You might be joking,” said Uri, “but, seriously, if there is one thing I lose sleep over is making sure that my powers are not misused or cause any harm. Rest assured that there is no way that my powers for bending spoons and forks could be harmful or dangerous.”

We were somewhat relieved.

“You are scientists aren’t you?” asked/sayed Geller. We confirmed: “mathematics and computer science”. “I love scientists and science,” said Geller, “I worked a lot with scientists all over the world, and like scientists I also try to expand human knowledge and human abilities in a similar way to what they do for the benefit of mankind.” Geller paused for a while and continued “I can even say that I am a scientist!” Then Geller paused again and said: “But there is one small group of scientists that I don’t like,” Uri Geller’s smile turned into a sad and angry expression, “skeptics, they have a destructive way of thinking. I hope you two are not skeptics.” “Well,” Avi said, “Gili is a skeptic, but don’t worry, Uri, he is a very nice skeptic.”

.. everybody came and all wanted to see Uri who is very famous, a very famous Israeli,…, so they all came to see him and they all wanted him to bend spoons, and he said I cannot do it right now, but they asked him could you bend our spoons, could you bend our spoons? So Uri said “all right” he stood in one corner of the restaurant and he simultaneously bent the spoons of all the people who were there! All right? Now, tell me, do you have an explanation how he worked it as a trick? If you give me a convincing explanation how he did it as a trick I would say, wow, he is a great magician! But he did it! I saw it! And I have seen it time and time again. So I think he has these special powers…

Netanyahu testifies about Geller.

Avi gave a great CS colloquium two days ago. Here with Noam Nisan and Orit Raz just before the lecture. (I will mention it in the next post.)

After many years, to cheer you up in these difficult times, another story in our corner “taxi and other stories”.

Meeting Michael H. at Rio

In my early years I used to guess how people looked by their names. I found it useful to associate an image to people but I always failed, when I finally met them they looked completely different, and then I usually changed the mental picture to the real image. In modern time people’s images are on the Internet. For example, I can see how my FB friends look based on their Facebook profile pictures.

In 2017 I was invited to the Brazilian Math colloquium in Rio and like the other speakers I stayed at the Everest hotel in Ipanema. I was there with my son Hagai, and before the event itself we spent a few days in near-by Peru. On the first day I met all other plenary speakers except one – Michael Hutchings – who was already my FB friend. And his FB profile picture looked like this

When I entered the elevator on my third day in Rio I saw a new face and I was pretty sure that this was Michael. He certainly looked like a mathematician. I was quite proud of my insight, and I wanted to surprise Michael with a funny introduction based on Michael’s Facebook profile picture.

“I suppose you do not carry a gun” I said.

Michael did not answer for a while, and then he answered “I think you are confusing me with somebody else”

Well, either Michael did not understand my subtle reference to his FB profile picture or, I gradually started thinking, was it possible that this person was not Michael Hutchings after all?

I decided to use the method of divide and conquer.

“Are you a m a t h e m a t i c i a n?” I asked

“No” the person replied, this time quickly. The elevator reached its destination and we both went in markedly different directions.

Later that day I met the real Michael Hutchings and to save you from similar misunderstandings, here is what Michael looks like.

From time to time I wonder what the other person thought about our conversation: “I suppose you do not carry a gun” – “I think you are confusing me with somebody else” – “Are you a m a t h e m a t i c i a n?” – “No” Did it make any sense to him? Did he change his views about mathematicians?

(I suppose that this amazing picture can serve as a metaphor also for life, for science, for human rights, for happiness and for a variety of other things.) Picture: AFP Suez Canal: the Ever Green ship blockage.

To cheer you up, in these difficult times, here are (in two parts) some mathematical news that I heard in personal communications or on social media. (Maybe I will write later, in more details, about few of them that are closer to combinatorics.)

Zvi (Zvika) was one of the first people that I met in 1971 at the university as a high school student and he gave me a lot of good advice and help. Here he shed light on an old mystery!

Abstract: A simple intuitive physical explanation is offered, of the stability of the inverted pendulum under fast violent vibrations. The direct description allows to analyze, both intuitively and rigorously, the effect of vibrations in similar, and in more general, situations. The rigorous derivations in the paper follow a singular perturbations model of mixed slow and fast dynamics. The approach allows applications beyond the classical inverted pendulum model.

I first heard about the stability of the inverted pendulum under fast violent vibrations from Sylvia Serfaty in connection with my study of “forehead-football.” See this post. Let me mention with pride that Endre Szemeredi, who is a fan of football in general (and a capable player), is also a fan of my forehead-football idea.

Imre Bárány, William Steiger, and Sivan Toledo the cocked hat

Abstract (arXive): We revisit the cocked hat — an old problem from navigation — and examine under what conditions its old solution is valid.

Katie Clinch, Bill Jackson, Shin-ichi Tanigawa: Maximal Matroid Problem on Graphs

In mid January, we had a great lecture by Shin-ichi Tanigawa (University of Tokyo). I certainly plan to blog about it. Here is the abstract.

The problem of characterizing the 3-dimensional generic rigidity of graphs is one of the major open problems in graph rigidity theory. Walter Whiteley conjectured that the 3-dimensional generic matroid coincides with a matroid studied in the context of bivariate splines. In this talk I will show a solution to the characterization problem for the latter matroid.

I will explain the idea of our characterization from the view point of constructing maximal matroids on complete graphs. Specifically, for a graph H, a matroid on the edge set of a complete graph is called an H-matroid if every edge set of each subgraph isomorphic to H is a circuit. A main theme of my talk will be about identifying and constructing a maximal H-matroid with respect to the weak order. This talk is based on a joint work with Bill Jackson and Katie Clinch.

Abstract:We study the harmonic polytope, which arose in Ardila, Denham, and Huh’s work on the Lagrangian geometry of matroids. We show that it is a (2n−2)-dimensional polytope with $latex (n!)^2 (1+1/2+⋯+1/n)$ vertices and $latex 3^n−3$ facets. We give a formula for its volume: it is a weighted sum of the degrees of the projective varieties of all the toric ideals of connected bipartite graphs with n edges; or equivalently, a weighted sum of the lattice point counts of all the corresponding trimmed generalized permutahedra.

This is very big news: twenty years after Smirnov’s result for the triangular grid, finally rotational invariance is proved for critical percolation on the square grid.

Authors: Hugo Duminil-Copin, Karol Kajetan Kozlowski, Dmitry Krachun, Ioan Manolescu, Mendes Oulamara

Abstract: In this paper, we prove that the large scale properties of a number of two-dimensional lattice models are rotationally invariant. More precisely, we prove that the random-cluster model on the square lattice with cluster-weight 1≤q≤4 exhibits rotational invariance at large scales. This covers the case of Bernoulli percolation on the square lattice as an important example. We deduce from this result that the correlations of the Potts models with q∈{2,3,4} colors and of the six-vertex height function with Δ∈[−1,−1/2] are rotationally invariant at large scales.

Noise sensitivity for planar percolation without Fourier

Endre Szemeredi sometimes say that we should try to avoid the use of his regularity lemma “at all costs”. Similarly, we should try to avoid Fourier tools if we can. Vincent and Hugo could!

Abstract: Consider critical Bernoulli percolation in the plane. We give a new proof of the sharp noise sensitivity theorem shown by Garban, Pete and Schramm. Contrary to the previous approaches, we do not use any spectral tool. We rather study differential inequalities satisfied by a dynamical four-arm event, in the spirit of Kesten’s proof of scaling relations. We also obtain new results in dynamical percolation. In particular, we prove that the Hausdorff dimension of the set of times with both primal and dual percolation equals 2/3 a.s.

Harry Kesten famously proved that the critical probability for planar percolation is 1/2. Planar duality is crucial. Many people expected or speculated that a similar statement for -dimensions holds if we replace “connectivity” by some statement about dimensional homology. This is what the new paper does.

(Next part: Topology, graph theory, algebra, Boolean functions, and Mathematics over the media.)

The Abel Prize was awarded earlier today to László Lovász and Avi Wigderson

“for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics.”

Congratulations to Laci and Avi, to their families, and to the communities of theoretical computer science and combinatorics. Let me quote one more sentence from the citation:

“They have both made fundamental contributions to understanding randomness in computation and in exploring the boundaries of efficient computation.”

I will not write today about computer science or mathematics but rather I will show you some pictures and give some links. (I will add most of the pictures later today.)

(Update 1) Links: NYT (Kenneth Chang), Quanta Magazine (Kevin Hartnett), (and many other places); blogs: In theory (Finally, a joy), Computational Complexity (Ohh Boy), Shtetl Optimized, Igor Pak. Luca’s post describes very nicely how early results of Laci and Avi interlace. (Update 2) A very nice post on GLL featuring Dorit Aharonov as the post’s “saint patron”, and connections to people and papers of quantum computation.

Abstract: We propose a general tensor network method for simulating quantum circuits. The method is massively more efficient in computing a large number of correlated bitstring amplitudes and probabilities than existing methods. As an application, we study the sampling problem of Google’s Sycamore circuits, which are believed to be beyond the reach of classical supercomputers and have been used to demonstrate quantum supremacy. Using our method, employing a small computational cluster containing 60 graphical processing units (GPUs), we have generated one million correlated bitstrings with some entries fixed, from the Sycamore circuit with 53 qubits and 20 cycles, with linear cross-entropy benchmark (XEB) fidelity equals 0.739, which is much higher than those in Google’s quantum supremacy experiments.

Congratulations to Feng Pan and Pan Zhang for this remarkable breakthrough!

Of course, we can expect that in the weeks and months to come, the community will learn, carefully check, and digest this surprising result and will ponder about its meaning and interpretation. Stay tuned!

Here is a technical matter I am puzzled about: the paper claims the ability to compute precisely the amplitudes for a large number of bitstrings. (Apparently computing the amplitudes is even more difficult computational task than sampling.) But then, it is not clear to me where the upper bound of 0.739 comes from? If you have the precise amplitudes it seems that you can sample with close to perfect fidelity. (And, if you wish, you can get a F_XEB score larger than 1.)

Update: This is explained just before the discussion part of the paper. The crucial thing is that the probabilities for the 2^21 strings are distributed close to Porter-Thomas (exponentials). If you take samples for them indeed you can get samples with F_XEB between -1 and 15. Picking the highest 10^6 strings from 2^21 get you 0.739 (so this value has no special meaning.) Probably by using Metropolis sampling you can get (smaller, unless you enlarge 2^21 to 2^25, say) samples with F_XEB close to 1 and size-biased distribution (the distribution of probabilities of sampled strings) that fits the theoretical size biased distribution. And you can also use metropolis sampling to get a sample of size 10^6 with the correct distribution of probabilities for somewhat smaller fidelity.

The paper mentions several earlier papers in this direction, including an earlier result by Johnnie Gray and Stefanos Kourtis in the paper Hyper-optimized tensor network contraction and another earlier result in the paper Classical Simulation of Quantum Supremacy Circuits by a group of researchers Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, and Jianxin Chen, from Alibaba co. Congratulations to them as well.

I am thankful to colleagues who told me about this paper.

There is a very famous conjecture of Irving Kaplansky that asserts that the group ring of a torsion free group does not have zero-divisors. Given a group G and a ring R, the group ring R[G] consists of formal (finite) linear combinations of group elements with coefficients in the ring. You can easily define additions in R[G], and can extend the group multiplication to R[G], which makes the group ring a ring. (And if R is a field, R[G] is an algebra, called group-algebra.)

Kaplansky’s zero divisor conjecture asserts that if G is torsion-free and K is a field then K[G] has no zero-divisors.

Irving Kaplansky

This conjecture was made in the 1950s or even 1940s. It is known to hold for many classes of groups. If G has torsion, namely an element g of order n, then .

Kaplansky made also in the 50s two other conjectures.

Kaplansky’s unit conjecture asserts that if G is torsion-free and K is a field the only units in the face ring of K[G] are of the form kg where k in a non-zero element in the field and g is an element of the group,

Kaplansky’s idempotents conjecture asserts that if G is torsion-free and K is a field then the only idempotents in K[G] are 0 and 1.

If G has torsion, namely an element g of order n, then $(1-g)(1+g+g^2+\cdots +g^{n-1})=0$. It is not very hard to see that the unit conjecture implies the zero-divisor conjecture which in turn implies the idempotent conjecture.

A few days ago, Giles Gardam gave a great, very pleasant, lecture about Kaplansky’s conjectures.

After introducing the conjectures themselves, Giles explained that these conjectures are related to several other conjectures like the Baum-Connes conjecture or Farrell-Jones and a conjecture of Atiyah. So this implies, for example that the zero divisors conjecture holds for residually torsion free solvable group. Now, as an aside let me say that it is good to know what does it mean for a property X to say that a groups G is “residually X”. I tried to explain it in this post. But I myself forgot, so together with you, devoted readers, I will go to the old post to be reminded. Let’s get reminded also of the easier concept of “virtually X”.

The assertion of Kaplansky’s unit conjecture holds for torsion-free unique-product groups. The unique product property says the following if A and B are finite subsets of the group there is an element c that can be written in a unique way as c=ab where a belongs to A and b belongs to B.

This concept was defined in 1964 by Rudin and Schneider and for two decades it was not even known that there are groups without the unique-product property. The first example of a group without this property was discovered by Rips and Segev.

Let me make a small diversion here. From time to time I talk about results by people I personally know and usually I don’t mention that in the posts. For example, in the post about Yuansi Chen’s work on Bourgain’s slicing conjecture and the KLS conjecture I personally knew about 70% of the heroes in that story (update: 19:25). In fact, both Bo’az Klartag and me are living in the very same apartment building in Tel Aviv. (Officially, I am in number 9 and Bo’az is in number 7 but topologically it is the same building.)

But here I must mention that Yoav Segev is my class mate in undergraduate years and is now a Professor at Ben Gurion University in Beer-Shava. He is responsible to one of the final steps in the classification program, to knocking down several other conjectures in algebra, and also to works on fixed-point free actions of non solvable groups on simplicial complexes. This last topic is close to my own interests and from time to time we chat about it. And of course, Ilya Rips is extraordinary mathematician and we are emeritus colleagues at HUJI – see this post about Ripsfest.

So let me go back to Giles’s lecture. Giles discussed two classes of examples of groups without the unique product property. And at minute 49 of the (50-minute) lecture Giles said: “I am nearly at the end of the talk and its time for me to tell you what’s new, um, what’s my contribution to this story, um, so I am really happy to be able to announce today for the first time, that, in fact, the unit conjecture is false.”

Theorem (Giles Gardam, 2021): Let P be the torsion-free virtually abelian group

And lt K be the field with two elements. Then there is a nontrivial unit in K[G], so that both and have support of size 21.

(This group does satisfy the zero-divisor conjecture.)