Let me tell you about three of my recent papers

michaelrabin

 

Let me tell you briefly about three of my papers that were recently accepted for publication. Relative Leray numbers via spectral sequences with Roy Meshulam, Helly-type problems with Imre Bárány, and Statistical aspects of quantum supremacy experiments with Yosi Rinott and Tomar Shoham.

Relative Leray numbers via spectral sequences

We extend the topological colorful Helly theorem to the relative setting. Our main tool is a spectral sequence for the intersection of complexes indexed by a geometric lattice. 

Roy and I have a long term project of studying topological Helly type theorems. Often, results from convexity give a simple and strong manifestation of theorems from topology: For example, Helly’s theorem manifests the nerve theorem from algebraic topology, and Radon’s theorem can be regarded as an early “linear” version of the Borsuk–Ulam theorem. We have a few more “linear” theorems in need of topologizing on our list. Actually the paper already appeared in Mathematika on June 26, 2021. It is dedicated to our dear colleague and friend  Michael O. Rabin. 

Dedicated to Michael O. Rabin, a trailblazing mathematician and computer scientist

Helly type problems, to appear in the Bulletin of the American Mathematical Society 

We present a variety of problems in the interface between combinatorics and geometry around the theorems of Helly, Radon, Carath ́eodory, and Tverberg. Through these problems we describe the fascinating area of Helly-type theorems, and explain some of its main themes and goals.

Imre and I have long term common interest in Helly-type problems and often discussed it since we first met in 1982.  We wrote a first joint paper in 2016 and last year we wrote two additional papers with Attila Por.  Last year Imre wrote a great book  “Combinatorial convexity” (AMS, 2021, in press) largely devoted to Helly-type theorems. As for me, I plan on gradually writing on open problems related to my areas of interest. (See these slides for some problems.)   

Statistical aspects of quantum supremacy experiments

Yosi Rinott, Tomer Shoham and I started this project about a year an a half ago. Our paper have now been accepted to Statistical Science where you can download the accepted version along many other future papers. This is my second paper in Statistical Science. The first one was “Solving the bible code puzzle” with Brendan McKay, Dror Bar-Nathan and Maya Bar-Hillel, that appeared in 1999.     

In quantum computing, a demonstration of quantum supremacy (or quantum advantage) consists of presenting a task, possibly of no practical value, whose computation is feasible on a quantum device, but cannot be performed by classical computers in any feasible amount of time. The notable claim of quantum supremacy presented by Google’s team in 2019 consists of demonstrating the ability of a quantum circuit to generate, albeit with considerable noise, bitstrings from a distribution that is considered hard to simulate on classical computers. Very recently, in 2020, a quantum supremacy claim was presented by a group from the University of Science and Technology of China, using a different technology and generating a different distribution, but sharing some statistical principles with Google’s demonstration.

Verifying that the generated data is indeed from the claimed distribution and assessing the circuit’s noise level and its fidelity is a statistical undertaking. The objective of this paper is to explain the relations between quantum computing and some of the statistical aspects involved in demonstrating quantum supremacy in terms that are accessible to statisticians, computer scientists, and mathematicians. Starting with the statistical modeling and analysis in Google’s demonstration, which we explain, we study various estimators of the fidelity, and different approaches to testing the distributions generated by the quantum computer. We propose different noise models, and discuss their implications. A preliminary study of the Google data, focusing mostly on circuits of 12 and 14 qubits is given in different parts of the paper

 

Posted in Combinatorics, Convexity, Geometry, Quantum, Statistics | Tagged , , , , | Leave a comment

Mathematical news to cheer you up

Anna-Kiesenhofer-Olympics-2021-930x620

1.  Anna Kiesenhofer, a PhD mathematician researching PDEs at Ecole Polytechnique Federale Lausanne (EPFL), won the gold medal in the women’s bicycle road race at the Olympics.

Here are two trivia question: a) Which hero of a recent post over here is related to Kiesenhofer’s mathematical side? b) Name another famous connection between EPFL-mathematics and sport.

2. János Nagy and Péter Pál Pach proved the Alon-Jaeger-Tarsi conjecture via group ring identities

The abstract says it all: In this paper we resolve the Alon-Jaeger-Tarsi conjecture for sufficiently large primes. Namely, we show that for any finite field F of size 61<|F|79 and any nonsingular matrix M over F there exists a vector x such that neither x nor Ax has a 0 component.

3. Michael Simkin asymptotically solved the n-queens problem! (We mentioned this classic problem and earlier progress by Zur Luria in this post.)

Abstract: The n-queens problem is to determine {\mathcal Q}(n), the number of ways to place n mutually non-threatening queens on an n \times n board. We show that there exists a constant α=1.942±3×10-3 such that {\mathcal Q}(n)=((1 \pm o(1))n e ^{-\alpha})^n. The constant α is characterized as the solution to a convex optimization problem in {\mathcal P}([−1/2,1/2]2), the space of Borel probability measures on the square. The chief innovation is the introduction of limit objects for n-queens configurations, which we call “queenons”. These are a convex set in \mathcal P([−1/2,1/2]2). We define an entropy function that counts the number of n-queens configurations that approximate a given queenon. The upper bound uses the entropy method. For the lower bound we describe a randomized algorithm that constructs a configuration near a prespecified queen on and whose entropy matches that found in the upper bound. The enumeration of n-queens configurations is then obtained by maximizing the (concave) entropy function in the space of queenons. Along the way we prove a large deviations principle for n-queens configurations that can be used to study their typical structure.

sun

Intermission: the sun over Tel Aviv sea

4. Boris Bukh demonstrated Extremal graphs without exponentially-small bicliques

Abstract: The Turán problem asks for the largest number of edges in an $latex n$-vertex graph not containing a fixed forbidden subgraph F. We construct a new family of graphs not containing K_{s,t}, for t=C^s, with  \Omega (n^{2-1/s}) edges matching the upper bound of Kövári, Sós and Turán. 

5. Michael Capalbo, Explicit 𝑁-vertex graphs with maximum degree 𝐾 and diameter [1+𝑜(1)]log𝐾-1 𝑁 for each 𝐾-1 a prime power,

Abstract:   Here we first present the solution of a long-standing open question–the explicit construction of an infinite family of N-vertex cubic graphs that have diameter [1+o(1)]log2 N. We then extend the techniques to construct, for each K of the form 2s+1 or K=ps+1; s an integer and p a prime, an infinite family of K-regular graphs on N vertices with diameter [1+o(1)]logK−1 N.

I missed this breakthrough in STOC 2019 but now it appeared in Combinatorica, and Nati told me about it.

6.  A beautiful survey article: Intersection Problems in Extremal Combinatorics: Theorems, Techniques and Questions Old and New, by David Ellis,

Abstract: The study of intersection problems in Extremal Combinatorics dates back perhaps to 1938, when Paul Erdős, Chao Ko and Richard Rado proved the (first) `Erdős-Ko-Rado theorem’ on the maximum possible size of an intersecting family of k-element subsets of a finite set. Since then, a plethora of results of a similar flavour have been proved, for a range of different mathematical structures, using a wide variety of different methods. Structures studied in this context have included families of vector subspaces, families of graphs, subsets of finite groups with given group actions, and of course uniform hypergraphs with stronger or weaker intersection conditions imposed. The methods used have included purely combinatorial ones such as shifting/compressions, algebraic methods (including linear-algebraic, Fourier analytic and representation-theoretic), and more recently, analytic, probabilistic and regularity-type methods. As well as being natural problems in their own right, intersection problems have connections with many other parts of Combinatorics and with Theoretical Computer Science (and indeed with many other parts of Mathematics), both through the results themselves, and the methods used. In this survey paper, we discuss both old and new results (and both old and new methods), in the field of intersection problems. Many interesting open problems remain; we will discuss several. For expositional and pedagogical purposes, we also take this opportunity to give slightly streamlined versions of proofs (due to others) of several classical results in the area. This survey is intended to be useful to PhD students, as well as to more established researchers. It is a personal perspective on the field, and is not intended to be exhaustive; we apologise for any omissions. It is an expanded version of a paper that will appear in the Proceedings of the 29th British Combinatorial Conference.

7.  An interview with me; interviewer Toufik Mansour.

 

 
 

Posted in Combinatorics, Sport, Uncategorized, Updates | 5 Comments

To Cheer You Up in Difficult Times 28: Math On the Beach (Alef’s Corner)

math-on-the-beach

Posted in Art, What is Mathematics | Tagged | Leave a comment

To cheer you up in difficult times 27: A major recent “Lean” proof verification

Lean is a functional programming language that makes it easy to write correct and maintainable code. You can also use Lean as an interactive theorem prover.” (See Lean’s homepage and see here for an introduction to lean.)

Kevin Buzzard’s blog XENA is largely devoted to lean. “The Xena project is an attempt to show young mathematicians that essentially all of the questions which show up in their undergraduate courses in pure mathematics can be turned into levels of a computer game called Lean.” (Perhaps this could also appeal to old mathematicians especially those interested in computer games 🙂 .)

Six months ago Peter Scholze proposed over XENA a project of verifying using Lean a certain involved proof he had (and was not even sure about), a few weeks ago he reported on an amazing progress that was achieved. This is great news! (I thank Tammy Ziegler for telling me about it.) For more on Lean see this Quanta Magazine article by Kevin Hartnett, and this GLL post. As a form of celebration, I posted an MO question on experimental mathematics (that renewed my older MO question).



KBPS

Kevin Buzzard and Peter Scholze

Posted in Algebra, Updates, What is Mathematics | Tagged , , | 4 Comments

To cheer you up in difficult times 26: Two real-life lectures yesterday at the Technion

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 h-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.

sc1

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

sc2

Posted in Combinatorics, Convex polytopes, Economics, Games, Rationality | Tagged | Leave a comment

To Cheer You Up in Difficult times 24: Borodin’s colouring conjecture!

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 r-degenerate if every subgraph has a vertex of degree at most r.

Every planar graph G can be coloured with five colours so that the union of every k colour classes, 1 \le k \le 4 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, 1 \le k \le 4 induces a stress free graph for generic embedding into R^{k-1}.

Grunbaum’s 1973 paper Acyclic colorings 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.

Posted in Combinatorics | Tagged , | Leave a comment

To cheer you up in difficult times 25: some mathematical news! (Part 2)

Topology

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).

Unknot recognition in quasi-polynomial time (The link is to the slides)

NP hardness for related questions regarding knots

This is a talk by Martin Tancer given at the Copenhagen-Jerusalem combinatorics seminar.

Title: The unbearable hardness of unknotting (link to the 2018 arXive paper)

Abstract:

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

Monumental work on Arnold’s conjecture

Arnold Conjecture and Morava K-theory by Mohammed Abouzaid, Andrew J. Blumberg

(I heard it from a retweet by Alex Kontorovich.)

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.

Graph theory

Large spanning graphs with odd degrees

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.

Here is an article about it in Quanta Magazine. And here is a Quanta Magazine article on the solution of the Erdos-Hajnal conjecture for pentagon-free graphs (that I mentioned in this post).

The Betti numbers of the independence complex of a ternary graph

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 Zhang proved 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.

For related advances see Alexander Engstrom, On the topological Kalai-Meshulam conjectureJinha Kim, The homotopy type of the independence complex of graphs with no induced cycle of length divisible by three

Here is a very nice survey by Paul Seymour and Alex Scott on chi-boundedness. Here is an earlier post on Trinity graphs and chi-boundedness.

A breakthrough in additive combinatorics

THP
Huy Tuan Pham

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 f(n) of colors needed to color the positive integers less than n so that n cannot be written as a sum of elements of the same color. Conlon, Fox and Pham  proved that f(n) is within a constant factor of n4/3φ(n)-1(log n)-1/3(loglog n)-2/3, where φ(n) is the Euler totient function. The paper is: 

The paper is: Subset sums, completeness and colorings,


P-adic local Langlands

Test Your Intuition: p-adic local Langlands edition!

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.

***************

Copenhagen-Jerusalem Combinatorics Seminar

It is my pleasure to invite you to the following talk:
**************************************************************************
Thursday, May 20 Time: 16:00-18:00 CET, Jerusalem +1
Location: Zoom: https://ucph-ku.zoom.us/j/69204766431

**************************************************************************

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.





Posted in Algebra, Combinatorics, Geometry, Number theory | 2 Comments

To cheer you up in difficult times 23: the original hand-written slides of Terry Tao’s 2015 Einstein Lecture in Jerusalem

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.)

tt-p1

The first page signed by Terry.

Addition:
Let me mention a very recent post with the timely title “Why you shouldn’t be too pessimistic” by Igor Pak about conjectures. (And earlier posts on Conjectures, here and here.)

Update: There were recent developments regarding this topic including a recent talk by Terry Tao at MSRI – here is the video, and a paper “Constructing Turing complete Euler flows in dimension 3 by Robert Cardona, Eva Miranda, Daniel Peralta-Salas, and Francisco Presas. Here is a related videotaped lecture.

The video of the lecture

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)

T.M. Krishna, Carnatic music (part 2, part3, part 4)

Tao-commentary

My comments about Tao’s conjecture.

the-wailing-wall-2009

With Terry, 2009. (See this post)Miranda

From a recent talk by Eva Miranda & Daniel Peralta-Salas

Posted in Analysis, Applied mathematics, Computer Science and Optimization, Physics, What is Mathematics | Tagged | Leave a comment

Alef Corner: ICM2022

icm2022Alef’s new piece for ICM 2022 will surely cheer you up!

Posted in Art, Combinatorics, Geometry, ICM2022 | Tagged , | Leave a comment

The probabilistic proof that 2^400-593 is a prime: a revolutionary new type of mathematical proof, or not a proof at all?

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:

2^{400}-593 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 2^{400}-593 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 2^{400}-593 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.

Update: Here is the video of the HUJI talk Avi Wigderson – The Value of Errors in Proofs. Our little discussion starts here (37.30 roughly untill 43:00).

What do you think?

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

Update: Interesting Facebook discussion; and another one;

593

Posted in Computer Science and Optimization, Controversies, Philosophy, What is Mathematics | Tagged , , | 15 Comments