After 16 months without lecturing to an audience in my same location, I gave yesterday two lectures at the Technion in front of a live audience (and some additional audience in remote locations). The main lecture was in COMSOC 2021, an international conference on computational social choice, and earlier I gave a guest lecture in Roy Meshulam’s class about simple polytopes. I also met many friends.

Reshef Meir who organized (with Bill Zwicker) COMSOC 2021 wrote:

Hi all,

today was beyond expectations – the first feeling of a real actual conference after almost a year and a half! We had about 40 people attending, viewing posters, and listening to talks. I truly hope this will return to be a common scene and that we can all meet face to face soon.

In my COMSOC lecture I talked about some earlier ideas and results in my work on social choice, starting with my paper with Ariel Rubinstein and Rani Spiegler on rationalizing individual choice by multiple rationals, and my subsequent attempt to use learnability as a tool for understanding choices of economic agents. This led to interesting questions on social choice that are discussed in this 2009 post.

In Roy’s course I explained -vectors of polytopes and the Dehn-Sommerville relations based on counting outdegrees of the graph of the polytope when we direct its edges based on a generic abstract objective function. I moved on to present a proof of Blind-Mani’s theorem that the graph of the polytope determines the full combinatorics. This proof is probably the one proof I presented the most and it is given in this 2009 post.

In my COMSOC lecture I described how to fill the two question marks in the table above.

An acyclic colouring of a graph is a colouring of its vertices so that the subgraph spanned on union of every two colour classes is acyclic (a forest). Grunbaum conjectured in 1973 that

Every planar graph has acyclic colouring with five colours.

This was proved by Borodin in 1976.

Borodin made the following stronger conjecture. Recall that a graph is -degenerate if every subgraph has a vertex of degree at most .

Every planar graph G can be coloured with five colours so that the union of every k colour classes, induces a (k-1)-degenerate graph.

Let me mention an intermediate conjecture in-between Grunbaum’s conjecture and Borodin’s

Every planar graph G can be coloured with five colours so that the union of every k colour classes, induces a stress free graph for generic embedding into .

Grunbaum’s 1973 paper Acycliccolorings of planar graphs is a very imaginative and highly cited paper. It was the first paper I ever refereed and I remember spending a lot of time reading it. Here is the link to Borodin’s paper On acyclic colorings of planar graphs. I am not sure what is the current world-record for the number of colours.

Quasi-polynomial algorithms for telling if a knot is trivial

Marc Lackenby announced a quasi-polynomial time algorithm to decide whether a given knot is the unknot! This is a big breakthrough. This question is known to be both in NP and in coNP. See this post, and updates there in the comment section.

Topology seminar, UC Davis, February 2021 and Oxford, March 2021 and today, May 20!16:00 CET, in the Copenhagen-Jerusalem combinatorics seminar (see details at the end of the post).

During the talk, I will sketch a proof that deciding if a diagram of the unknot can be untangled using at most k Riedemeister moves (where k is part of the input) is NP-hard. (This is not the same as the unknot recognition but it reveals some difficulties.) Similar ideas can be also used for proving that several other similar invariants are NP-hard to recognize on links.

Joint work with A. de Mesmay, Y. Rieck and E. Sedgwick.

An approach toward exotic differentiable 4-dim spheres

Lower bound for the number of fixed points of a map is a central theme in topology (and other areas) with many great results. The Lefshetz fixed point theorem tells you that a certain signed sum of the fixed points is bounded from below . For symplectic manifold Arnold’s conjecture asserts that the number of fixed point is bounded below from the sun of Betti numbers. This have led and is connected to tremendous mathematics.

Abstract (part): We prove that the rank of the cohomology of a closed symplectic manifold with coefficients in a field of characteristic p is smaller than the number of periodic orbits of any non-degenerate Hamiltonian flow.

Asaf Ferber and Michael Krivelevich solved an old conjecture in Graph theory. (In a 1994 paper by Yair Caro the problem is already referred to as part of the folklore of graph theory.)

Abstract: We prove that every graph G on n vertices with no isolated vertices contains an induced subgraph of size at least n/10000 with all degrees odd. This solves an old and well-known conjecture in graph theory.

A ternary graph (aka Trinity graph) has no induced cycles of length divisible by three. Chudnovsky, Scott, Seymour and Spirkl proved that for any ternary graph G, the number of independent sets with even cardinality and the independent sets with odd cardinality differ by at most 1. Hehui Wu and Wentao Zhangproved the stronger conjecture that for ternary graphs, the sum of Betti numbers of the independent complex is at most one. (Both conjectures were proposed by Roy Meshulam and me.) Congratulations to Hehui and Wentao and all other people mentioned in this post.

David Conlon, Jacob Fox and Huy Tuan Pham used a new unified approach to solve a variety of open problems around subset sums including the open problems of Burr and Erdős on Ramsey complete sequences (Erdős offered $350 for their solutions) and a problem of Alon and Erdős on estimating the minimum number of colors needed to color the positive integers less than so that cannot be written as a sum of elements of the same color. Conlon, Fox and Pham proved that is within a constant factor of n^{4/3}φ(n)^{-1}(log n)^{-1/3}(loglog n)^{-2/3}, where φ(n) is the Euler totient function. The paper is:

This post over Persiflage will test your intuition about 2-dimensional crystalline deformation rings. Since I couldn’t understand even the first sentence, I decided to ask my FB and HUJI friend to explain it to me, so I may try to write about it later. Actually, a better idea is that Persiflage will try to give a vastly non-technical explanation from scratch on p-adic local Langlands conjecture, and where it stands and why it matters. (To be clear, I am sure it is a great staff! And perhaps it is not possible to explain it to a wide audience. But it worth a try.)

Meanwhile it reminded me of the following story to which I apparently was a witness.

At the time of my birth, the medical approach was that mother and child needed to stay at the hospital for at least four nights and even for an entire whole week. After two nights at the hospital, my mother decided that she was ready to go home and got into a lengthy discussion with her doctor about it. At some point the exhausted doctor told her “Madam, I studied seven years in medical school, and I know what is good for you.” My mother was not impressed and replied: “Had I studied seven years in medical school, I would have been a medical doctor as well. And now, let me go home.” At the end, my mother (and myself) left the hospital on the third day. Years later this became the medical standard. (My own approach is to follow medical doctor’s instructions.)

Mathematics over the media

Ramanujan machine: machine learning for producing mathematical conjectures

This is a cool and very interesting direction by very very young Israeli mathematicians that was reported all over the media. (See, here for a Nature article.)

(There are various groups all over the world attempting to use machine learning to produce mathematical conjectures.)

A new approach for solving quadratic equations

I heard it (I think it was a year ago) from a Facebook post written by the prime minister of Singapore! And then I saw it in other places all over the media (here on the NYT). I like it, and, in fact, I like the many things Po-Shen Loh (who is my grand academic nephew) does in the service of mathematics.

Marc Lackenby: Unknot recognition in quasi-polynomial time **************************************************************************

Abstract:

I will outline a new algorithm for unknot recognition that runs in quasi-polynomial time. The input is a diagram of a knot with n crossings, and the running time is 2^{O((log n)^3)}. The algorithm uses a wide variety of tools from 3-manifold theory, including normal surfaces, hierarchies and Heegaard splittings. In my talk, I will explain this background theory, as well as explain how it fits into the algorithm.

In 2015 Terry Tao gave the Einstein lecture of the Israeli Academy for Science and Humanities. We got hold of the original signed hand-written slides of Terry’s lecture and we are happy to share them with you. The title of Tao’s talk was “Can the Navier-Stokes Equations Blow Up in Finite Time?”. Here are the original slides! (With an additional page with my comments.)

In general, the Academy holds very nice academic events that I enjoyed participating over the years (especially when I lived near by). The Einstein lecture is a yearly science lecture and occasionally it is given in mathematics. (The most recent mathematics lecture was given by Peter Sarnak and we will try to get hold of Peter’s slides as well.) There is also a yearly lecture named after Martin Buber in the humanities.

The topic of Tao’s lecture was discussed on Terry’s blog (also here and several other posts), here on my blog, on SO, on GLL, on Quanta Magazine, and in various other places. Tao conjectured that Navier-Stokes evolutions allows computation and therefore contrary to the famous conjecture do allow blow-up in finite time. I was curious about a way to formulate the negation of Tao’s conjecture (which would be a weaker version of the blow-up conjecture). I am not aware of recent developments regarding Tao’s approach.

So here are some more videos of lectures at the academy (some of them are in Hebrew).

When does Christianity begin? Paula Fredrikson

Ruth Gavison on “Constitutional Entrenchment of Israel‘s Vision?” (Hebrew)

Ron Aharoni on Mathematics, poetry, and beauty (Hebrew)

A conversation between David Harel (computer science) and Daniella London-Dekel (writer and cartoonist) in Hebrew.

Tamar Ziegler: bounded gaps between prime numbers (Hebrew)

Cana Werman: Hillel and Jesus (Hebrew)

Peter Sarnak: Randomness in number theory (English)

George Whitesides: Questions about the origin of life (English)

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.

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.