Snapshots from ICM2026

Posted on August 6, 2026 by Gil Kalai

ICM2026 in Philadelphia was, for me, a celebration of mathematics and people. I met many friends and colleagues, as well as several mathematical ideas and results. The nature of these meetings is that they are abrupt and random. (Some people don’t like it, but I do.) For me, mathematics and personal stories are often entangled. I tried to attend most of the plenary lectures and most of the combinatorics and computer science sectional lectures. Of course, given the vast wealth of mathematics (and my ignorance in most areas), this was also a humbling experience.

Are celebrations appropriate for me during these rather difficult times in my country (and some other places)? I tried to address this question in this post and this one.

Lior Silberman wrote nicely over Facebook his live experience from the congress. Lior’s scholarly understanding of most areas of mathematics is, of course, quite an advantage.

I enjoyed Annalisa Buffa’s lecture on New Challenges in Numerical Approximation of Partial Differential Equations.

A short stream of associations starting with quasi crystals interlaced with people I met.

Back in New York, Priya Subramanian told me about her interdisciplinary work on quasicrystals. She mentioned a physicist colleague, Ron Lifshitz from Tel Aviv University, whom I know well. In fact, I knew Ron’s parents, Hava Lifshitz and Assa Lifshitz, both noted chemists from HUJI. Assa was the head of the professors’ union during the time I also served on the union, and we had interesting negotiations for several years with the HUJI administration headed by my friend Menachem Magidor (then HUJI president), and also with the Finance Ministry.

A few days after meeting Priya, I met a hero of quasicrystals (and other areas), Jeff Lagarias, in Philadelphia. I have known Jeff since the 80s, and he pronounces my name “jill” (which I like coming from him, as well as from Gilles Pisier). Quasicrystals are closely related to the work of Dan Shechtman, a famous Israeli chemist, as well as to Penrose tilings and works on tilings and symbolic dynamics; the monumental work (master’s thesis!) of Shahar Mozes comes to mind.

I also met again Matt Foreman, whose research uniquely combines ergodic theory and set theory, and who is a close colleague of both Magidor and Benjy Weiss. I promised Matt to test my most outrageous conjecture about a proposed number-theoretic undecidability barrier on him.

Officers of the IMU and state delegates for the GA watch the football World Cup Final.

Convex polytopes with Günter Ziegler

On the train from NYC to Philly (If I may; I feel a little awkward to use the nickname “Philly” for Philadelphia), I spent a quality hour discussing the theory of convex polytopes with Günter Ziegler (who is now mainly occupied with being a university president). At the reception that evening, we met Frank Morgan (whom we both met at MIT in the 80s)—here are the three of us.

With Gunter Ziegler, Frank Morgan, and Imran Anwar. A few years ago, Imran hosted me in the John Conway Spirited Seminar series.

Meeting people for the first time

This time in Philadelphia, I met Maria Klawe and Nick Pippenger for the first time. (In 1990, I visited the CS group they founded at IBM San Jose for a year, but it was after they had already left). I met Robion Kirby for the first time, just hours after his work was prominently featured in Ciprian Manolescu’s lecture on knots and 4-manifolds.

I also met Erdal Arıkan, Fabio Martinelli, Nilma Nigam, David Kalaj, Yasuyuki Kawahigashi, Imran Anwar, Charles Bordenave, Ramon van Handel, and quite a few others for the first time. Among them, David Kalaj is probably my nearest lexicographic neighbor among all mathematicians (whose name is not identical to mine). Of course, I also met many old friends.

The Abacus Medal goes to Shayan Oveis Gharan

Shayan Oveis Gharan gave a beautiful Abacus Medal Lecture that, together with the invited lectures of Nima Anari and Cynthia Vinzant, added up to a mini-course on a fascinating new area of theoretical computer science and discrete mathematics with many connections (including to HDX). I hope to write about these three lectures in a future post. Heartfelt congratulations to Shayan and to all the prize winners.

Math for AI; AI for math, and the future of mathematics.

I missed the special panels on “Math for AI” and “AI for Math,” as well as most of the general audience lectures devoted to the AI revolution. (I did attend Terry Tao’s lecture, and I will try to catch up with the recordings). The ways in which AI will change mathematics was a large elephant in the room at the congress.*

Booths, Blackboards, Art, and AMR

With George Andrews

There was a large space for booths hosted by several organizations, alongside blackboards and mathematical art. One booth belonged to The Association for Mathematical Research (AMR). AMR is a nice international mathematical association that hosts a variety of activities and publishes several open-access journals.

When it was established 4–5 years ago, there were concerns that AMR was:

  • Anti-AMS
  • Anti-diversity
  • Anti-double-blind refereeing
  • Implicitly representative of right-wing politics

At the time, I did not join the AMR. However, a couple of years ago—after seeing that AMR runs nice activities that do not reflect those early fears and concerns—I did join. (Membership is free; becoming a member is mainly an act of support for AMR’s activities, as I am not aware of any special benefits for members.). Among the AMR founders are my long-time friends Abby Thompson and Joel Hass. I had interesting conversations with Abby about diversity, the situation at Davis since the October 7 war, and tolerance (or rather, the sad intolerance) toward a large variety of political views. See this post for a beautiful coloring conjecture by Abby Thompson.

Women at the ICM

When it comes to gender diversity, judging from the ICM participants and speakers, we are witnessing a positive change over the last five decades. While the main credit for that goes to women researchers themselves, what also made a big difference in the combinatorics community is the fact that extremely good teachers—like my Ph.D. supervisor Micha Perles, as well as Richard Stanley, Adriano Garsia, Herb Wilf, and others—were  welcoming to female students.

Erdal Arıkan’s talk

Erdal Arıkan gave a beautiful talk about polar codes. (See this 2010 post about polar codes which is among the greatest hits of my blog.)

Sarnak on Serre

Peter Sarnak gave a very enjoyable lecture about “Maestro Jean-Pierre Serre”.

Morning at the museum

I devoted one morning to the exquisite Philadelphia Museum of Art. 

Four talks related to additive combinatorics

I already wrote about Meka’s talk on the new bounds for Roth’s theorem. Tamar Ziegler gave a tour de force plenary talk about the Structure of Sets with an Unexpected Number of Arithmetic Patterns. Sara Peluse described some breakthrough results on the polynomial Szemerédi theorem, and Dor Minzer gave a talk on his work regarding 3-term arithmetic progressions with restricted gaps.

Tamar Ziegler’s lecture was a tour de force.

Many more talks related to combinatorics and computer science — stay tuned!

I plan to write separately about several talks on probabilistic combinatorics, extremal combinatorics, Ramsey theory, algebraic combinatorics, and various topics in theoretical computer science (including two talks on algorithmic game theory and a talk about quantum computation).

I am not sure what the quality of the recorded sectional lectures will be. (In Rio 2018, the recordings were of good quality, but unlike Rio, the recording this time is based on unmanned equipment.)

 

Rob Morris gave a great plenary talk on recent advances in Ramsey theory

__

*I usually rely on AI tools for editing. However, I decided to keep the reference to “a large elephant in the room” rather than the AI recommended edit: “a proverbial elephant in the room”.

Posted in Conferences, ICM2018 | Leave a comment

ICM 2026: A Magical Saturday Afternoon with Park, Braden and Proudfoot, and Meka

Posted on August 1, 2026 by Gil Kalai

Saturday afternoon, July 25, was quite magical for me: all three beautiful talks were closely related to my interests and to my own work. Here is a brief personal description of the lectures, with links to the slides and papers, followed by a more detailed account of each talk.

Jinyoung Park gave a beautiful talk entitled “Thresholds,” concerning an array of conjectures about the location of thresholds for monotone properties and some of their applications. She concentrated on three conjectures: the Kahn–Kalai conjecture, also known as the expectation-threshold conjecture; the second Kahn–Kalai conjecture; and Talagrand’s discrete convexity conjecture. Here are the links to the proceedings paper and the slides.

Tom Braden and Nicholas Proudfoot gave a beautiful talk entitled “Intersection Cohomology Without Spaces,” devoted to a major theme in algebraic combinatorics: geometric structures can survive, and remain powerful, even in settings where the geometry itself does not exist. They discussed three examples: Kazhdan–Lusztig polynomials for Coxeter groups, toric g-polynomials for polytopes, and Kazhdan–Lusztig–Stanley polynomials for matroids. Here are the links to the proceedings paper and to the slides.

Raghu Meka gave a beautiful talk entitled “Structure vs Randomness Redux.” The talk focused mainly on the new bounds of Meka and Zander Kelley for the density of sets of integers containing no three-term arithmetic progression. In my view, this is among the most important mathematical results of the past few years. The method relies on a new version of the “structure versus randomness” paradigm, and it has led to important progress in both additive combinatorics and theoretical computer science. Here are the links to the proceedings paper and the slides.

Breaking news

On another matter: OpenAI reported today on the solution of ten major mathematical problems.

Some personal comments

  1. I wrote about the Kahn–Kalai conjecture in several earlier posts. (In my lectures and posts, I was often imprecise about the distinction between the first and second conjectures.) Although both Jeff and I were skeptical about the conjecture, in our paper we proposed a program for proving it based on strong inverse forms of discrete isoperimetric inequalities. The central inverse conjecture, Conjecture 6(a) in our paper, is still open, although some stronger versions (6(b) and 6(c)) turned out to be false. Another part of the program, Conjecture 7, was also refuted. This was the subject of our first AI+Polymath project, in which the counterexample was found with the help of AI; see this post.
  2. Of the three topics discussed by Tom and Nicholas, the one I have studied most closely is the second: toric g-vectors of polytopes. Beyond the major achievement of extending the theory from rational polytopes to arbitrary polytopes, an important remaining challenge is to extend it further to strongly regular CW-spheres—that is, regular CW-spheres in which the intersection of any two cells is itself a cell. Karim Adiprasito’s solution of the g-conjecture for triangulated spheres—see this post and this one—may offer hope in this direction. Another important problem is to understand the combinatorial consequences of the results arising from algebraic geometry, whether “with spaces” or “without spaces.” See also this post.
  3. I have followed progress on Roth’s theorem and Szemerédi’s theorem for many years, including here on the blog. (I reported on the Kelley-Meka breakthrough in this 2023 post, and see, for example, also  this 2020 post; this 2010 post; this 2009 post; , and this 2016 post.) From time to time, I even tried to work on these problems myself.
  4. I have many fond memories connected with the mathematics of these three lectures, with the speakers, and with many of the other mathematicians involved.

Let me move now to a more detailed description of the three talks.

With Jinyoung Park and Hari Bercovici

Jinyoung Park: Thresholds

Jinyoung Park’s lecture, simply titled “Thresholds,” was organized around the question: What drives thresholds? Let X be a finite set and let X_p be the random subset obtained by choosing every element independently with probability p. For an increasing family {\cal I}\subseteq 2^X, its threshold p_c({\cal I}) is defined by \mu_p({\cal I})=1/2. A basic lower bound comes from the first-moment method. We call {\cal I}p-small if it can be covered by simple witnesses S whose total expected contribution satisfies \sum_{S\in{\cal G}}p^{|S|}\leq 1/2, and we let q({\cal I}) be the largest such p. Park discussed three fundamental questions concerning the relation between this simple expectation bound and the actual threshold.

The first question was the Kahn–Kalai conjecture, which asserted that the first-moment bound always determines the threshold up to a logarithmic factor. In its strengthened form, proved by Park and Huy Tuan Pham,

p_c({\cal I})\leq Cq({\cal I})\log \ell({\cal I}),

where \ell({\cal I}) is the size of the largest minimal member of {\cal I}. Earlier, Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Park had proved Talagrand’s fractional version, replacing ordinary covers by fractional covers. The dual language of spread measures turned out to be particularly powerful: once one constructs a probability distribution on the desired combinatorial structures for which no fixed set of elements occurs too often, the threshold theorem can be applied. This circle of ideas gives remarkably short routes to the correct threshold orders for perfect hypergraph matchings, Hamiltonian cycles, bounded-degree spanning trees, and several other difficult problems. The logarithmic factor cannot in general be removed, as illustrated by coupon-collector phenomena.

The second Kahn–Kalai conjecture is more concrete and remains open. Given a graph H, let p_{\rm E}(H) be the smallest p for which the expected number of copies in G(n,p) of every subgraph F\subseteq H is at least 1/2. Clearly p_{\rm E}(H)\leq p_c(H), and the conjecture asserts that

p_c(H)\leq C p_{\rm E}(H)\log v_H,

where v_H is the number of vertices of H. This is stronger than the general theorem because it asks us to use only the obvious subgraph witnesses, rather than arbitrary and possibly nonsymmetric covers. Recent work of Quentin Dubroff, Jeff Kahn, and Park proves the bound with an additional factor (\log n)^2, and proves the conjectured bound itself in the sparse regime p_{\rm E}(H)<1/(3n). Thus the remaining question is whether the complicated abstract witnesses defining q({\cal I}) can always be replaced, at constant cost, by the natural subgraphs of H.

Park’s third theme was Talagrand’s discrete convexity conjecture. For a decreasing family {\cal D}\subseteq 2^X, let

{\cal D}(k)={A_1\cup\cdots\cup A_k:A_1,\ldots,A_k\in{\cal D}},

and let {\cal D}^{(k)}=2^X\setminus{\cal D}(k).

The conjecture says that there are universal constants k and L such that, whenever {\cal D} has sufficiently large \mu_p-measure, the exceptional family {\cal D}^{(k)} is (p/L)-small. In words, boundedly many unions of members of a large decreasing family should cover almost the entire discrete cube, apart from an exceptional set whose smallness has an explicit first-moment explanation. The Park–Pham theorem gives a related statement with k=1 but with a necessary logarithmic loss in p; Talagrand’s conjecture predicts that allowing a bounded number of unions eliminates this loss. Talagrand described this as his “lifetime favorite problem,” and it remains open.

Tom Braden, Nicholas Proudfoot, with Pierre Deligne and George Lusztig

Tom Braden and Nicholas Proudfoot: Intersection Cohomology Without Spaces.

The second lecture, by Tom Braden and Nicholas Proudfoot, was entitled “Intersection Cohomology Without Spaces.” Ordinary cohomology behaves beautifully for smooth projective varieties, satisfying Poincaré duality, the hard Lefschetz theorem, and the Hodge–Riemann relations. For singular varieties, ordinary cohomology may lose these properties, but intersection cohomology restores them. Besides the global groups IH^*(X), one has local intersection cohomology groups  IH^*(X,p), which measure the singularity of X near p. Their graded dimensions often assemble into polynomials of central importance in combinatorics and representation theory.

Braden and Proudfoot presented three parallel examples. For Coxeter groups one obtains the Kazhdan–Lusztig polynomials; for convex polytopes one obtains Stanley’s g-polynomials; and for matroids one obtains the Kazhdan–Lusztig polynomials of matroids. All three belong to Stanley’s general theory of Kazhdan–Lusztig–Stanley, or KLS, polynomials associated with a ranked poset and a suitable collection of polynomials called a P-kernel. The KLS-polynomials f_{xy}(t) are defined recursively, together with the crucial degree condition

\deg f_{xy}(t)<\frac{{\rm rank}(y)-{\rm rank}(x)}{2}.

From their recursive definitions it is far from evident that their coefficients should be nonnegative. Geometry explains this by identifying them with Poincaré polynomials

f_{xy}(t)=\sum_{i\geq 0}t^i\dim IH^{2i}(X_y,p_x)

of appropriate local intersection cohomology groups.

The relevant geometric spaces exist only in special cases. For Weyl groups they are Schubert varieties in flag varieties; for rational polytopes they are toric varieties; and for realizable matroids they are arrangement Schubert varieties. But the combinatorial polynomials make sense for arbitrary Coxeter groups, nonrational polytopes, and nonrealizable matroids, where no corresponding algebraic variety exists. The remarkable development described in the lecture is that one can nevertheless construct the intersection cohomology groups themselves: by Soergel bimodules or moment-graph sheaves for Coxeter groups, by intersection cohomology sheaves on fans for polytopes, and by intersection cohomology modules for matroids. Thus the title “intersection cohomology without spaces” is quite literal: the algebraic and combinatorial shadows of the geometric theory continue to exist even after the underlying geometric space has disappeared.

The common framework uses sheaves of graded modules on finite posets. The strata of a variety are replaced by the elements of the poset, and the intersection cohomology sheaf is constructed inductively: after the data have been defined above an element x, the stalk at x is obtained as a minimal free module mapping onto the already known boundary data. This elementary-looking construction is only the beginning. The deep part is proving that the resulting graded vector spaces have the required dimensions, and this demands combinatorial analogues of hard Lefschetz and the Hodge–Riemann relations. These theories give much more than coefficientwise nonnegativity. For example, intersection cohomology of matroids was a central ingredient in the proof of the Dowling–Wilson top-heavy conjecture: if {\cal L} is the lattice of flats of a rank-d matroid, then

|{\cal L}^i|\leq |{\cal L}^{d-i}|\qquad\text{for }i\leq d/2.

The lecture offered a striking illustration of a major theme in modern combinatorics: geometric structures can survive, and remain powerful, even in settings where the geometry itself does not exist.

Remark (for the experts): The construction of the IH modules of a matroid that Tom and Nicholas outlined in the final slides (especially 23 and 24) is not the one that appears in the paper “Singular Hodge theory for combinatorial geometries”. (The resulting modules are the same for the two constructions.) They are currently finishing the papers with the new construction, to be posted soon.

Raghu Meka

Raghu Meka: Structure vs Randomness Redux.

Raghu Meka’s lecture was entitled “Structure vs Randomness Redux.” The classical structure-versus-randomness paradigm says that a complicated mathematical object can either be decomposed into structured pieces or shown to behave like a random object. Meka described a new and remarkably successful version of this paradigm, developed in works with Amir Abboud, Nick Fischer, Zander Kelley, and Shachar Lovett. Its central principle is

\text{\bf spreadness implies mixing}.

Roughly speaking, an object is spread if its density does not increase substantially when we restrict it to any large natural substructure—an affine subspace or a Bohr set for additive problems, and a rectangle for matrices. A spread object need not itself look random. The surprising assertion is that after combining two spread objects, by convolution or matrix multiplication, the result becomes close to uniform.

The first application was the classical problem of three-term arithmetic progressions. How large can a set A\subseteq [N] be if it contains no distinct a,b,c satisfying

a+b=2c?

Behrend’s celebrated construction gives progression-free sets of density 2^{-O(\sqrt{\log N})}. After a long sequence of results beginning with Roth’s theorem, the best upper bounds remained only polylogarithmic in N. Kelley and Meka made a striking jump to the stretched-exponential bound

|A|\leq N\cdot 2^{-\Omega((\log N)^\beta)}

for some absolute constant \beta>0. The proof first passes to finite vector spaces. There, either A has increased density on a low-codimensional affine subspace, or A is spread. In the latter case its normalized convolution satisfies, schematically,

|\mu_A*\mu_A-1|_k\ll 1,

and this mixing forces many solutions to x+y=2z. Thus one obtains a particularly clean density-increment argument: either we already have many progressions, or we move to a smaller ambient space where the set is denser.

A key ingredient in this theory is a new decoupling inequality. The quantities one wants to estimate often involve products such as

f(x,y)f(y,z)f(z,x),

in which the factors are dependent because they share variables. Decoupling replaces such an expression by related expressions involving more independent copies of the variables, where analytic estimates are much easier to apply. Two further ideas are essential. Spectral positivity converts unexpectedly small values into comparable upward deviations, which can drive a density increment; and sifting uses dependent sampling to locate the substructure on which this increased density occurs. These tools make the slogan “spreadness implies mixing” applicable far beyond ordinary additive convolution.

The final application concerned finding triangles and Boolean matrix multiplication. For a tripartite graph with adjacency functions A(x,y), B(y,z), and C(x,z), the normalized number of triangles is

{\mathbb E}_{x,y,z} A(x,y)B(y,z)C(x,z).

Abboud, Fischer, Kelley, Lovett, and Meka proved a new spread regularity lemma: every graph can be decomposed algorithmically into a controlled number of pieces, each of which is either sparse or spread. Sparse pieces can be handled directly, while on spread pieces the product of the relevant adjacency matrices mixes, making triangle detection easy. This leads to a combinatorial algorithm for Boolean matrix multiplication, and hence for triangle detection, with running time

\frac{n^3}{2^{\Omega((\log n)^{1/7})}},

a super-polylogarithmic improvement over the earlier combinatorial algorithms. The broader message of Meka’s lecture was that this new version of structure versus randomness provides a common explanation for breakthroughs in additive combinatorics, communication complexity, and fast algorithms.

 

Posted in Combinatorics, Computer Science and Optimization, Convex polytopes, Geometry, ICM2026, Probability | Tagged , , , | 1 Comment

Various News Items

Posted on July 23, 2026 by Gil Kalai

ICM 2026 starts today in Philadelphia; ICM 2030 will be in Glasgow

I am now in Philadelphia after a two-day meeting in New York of the General Assembly of the IMU (International Mathematical Union). Among its many activities, the IMU organizes the ICM (International Congress of Mathematicians).

ICM 2026 starts tomorrow later today (Thursday, July 23) here in Philadelphia, and it was just announced that ICM 2030 will take place in Glasgow. I will try to (slowly) blog about ICM 2026, continuing the tradition of my posts on ICM 2018 and ICM 2022. Yesterday there was an impressive reception event and I had the opportunity to reconnect briefly with many old friends.

A lecture at Columbia University

Yesterday I gave a lecture at Columbia University to a group of brilliant students, followed by a lively discussion. I spoke about some old problems and results in discrete geometry and reflected on how our understanding of them has evolved over the years.

Two quantum items

Here is a draft of my recent paper, The Fully Depolarizing Noise Conjecture for Entangled Physical States: A Twenty-Year Perspective. As always, comments and corrections are most welcome.

Amit Hagar (a philosopher of science from Indiana University) has written an interesting paper entitled The NISQ Trap: Eight Years of Demonstrations the Hardware was Built to Lose. (There is a post about it and an interesting discussion on Shtetl-Optimized.) This joins an earlier paper of Amit’s from 2009, Active Fault-Tolerant Quantum Error Correction: The Curse of the Open System and his subsequent book on the subject.

A lecture for Furstenberg’s birthday

I gave a talk in Hebrew at an evening celebrating Hillel Furstenberg’s 90th birthday. The talk was about Furstenberg’s contributions to enumerative combinatorics and their recent applications to algebraic circuit complexity. Here are the slides, and here is the raw video of the event. (My lecture 2:13:00.)

AI and math news

Two significant items: The Jacobian conjecture has been disproved (Claude; see this enlightening blog post by Terry Tao); the double cover conjecture has been proved (OpenAI).

Posted in AI, Conferences, ICM2026, Quantum, Updates | 2 Comments

Micha A. Perles 90th Birthday Meeting

Posted on July 16, 2026 by Gil Kalai

Last Monday we had  an afternoon session of the Annual Meeting of the Israeli Mathematical Society celebrating Micha Perles’ 90th birthday. The speakers were Nati Linial, me, Noga Alon,  Ron Adin, and Rom Pinchasi. There was a very nice attendance and quite a few former students of Micha came to the event.

Some photos

  

In the top row Micha with eleven former Ph. D. students and with five former women Ph. D. students. Below: lectures, greetings, and the audience.

The lectures

Nati Linial, Adventures with polytopes

Abstract: To the best of my recollection, I first heard about polytopes only when I started to attend Micha’s seminar, but with time, I found myself studying them myself. Fondly remembering the many things that I learned from Micha, I will tell about my most recent foray into this realm.

The n \times n bi-stochastic matrices form a polytope, in which every permutation matrix is clearly a vertex. The Birkhoff-von-Neumann theorem says that this exhausts the list of vertices. An n \times n \times n array of non-negative reals is called tri-stochasic if every row, column, and shaft in it sums to 1. These arrays form a polytope too, where every Latin squares is clearly a vertex. However, as we show, Latin squares are only a vanishingly small minority of the vertices.

Joint with Zur Luria and Maya Trakhtman arXiv:2604.09290. Nati’s Slides.

Gil Kalai, Reflections on some old problems and results

Abstract: I will describe some problems and results of Micha A. Perles, and his students about polytopes, convex sets and point configurations, from the seventies and eighties of the 20th century, and some progress made over the past decades.

My slides.

Noga Alon, Micha and shattering

Abstract: The Sauer-Perles-Shelah lemma is a fundamental result in extremal combinatorics with applications in discrete geometry, computional learning, probability, combinatorics, model theory, property testing, social choice, and more. After very brief comments about the original result, I will describe some recent variants and extensions.

Noga’s slides.

Ron Adin, Circular sorting

Abstract: What is the maximal number of steps required to sort n labeled points on a circle, by swapping points in adjacent positions? What if we swap adjacent values, rather than adjacent positions? What if we allow arbitrary (not necessarily adjacent) swaps?
These are circular analogues of well-known sorting problems, with applications in various computational sciences. We will describe exact results, as well as bounds, obtained using combinatorial, probabilistic and number theoretic methods.

Based on joint works with Noga Alon, Eli Bagno and Yuval Roichman. Ron’s slides.

Rom Pinchasi, 30 years later– on the occasion of the 90th anniversary of Micha Perles

Abstract: In honor of Micha Perles’ 90th anniversary we will bring some of the many anecdotes that were not mentioned by previous speakers. We will combine these fun and beautiful memories from 30 years ago with some research and results that constitute my own private memories with Micha. The 90th anniversary of Micha Perles is a milestone for many people in the community of discrete geometry and combinatorics. Could it also be the end of the classical era of mathematics in some sense? We will know the answer by the 100th anniversary of Micha Perles. I promise many more anecdotes then.

Rom Pinchasi’s lecture had three parts. The first part was about the Kupitz-Perles conjecture (that I also mentioned more briefly in my lecture; see this post and this one). The second part was about Rom’s M. Sc. thesis about skips (דילוגים) in planar point configurations (but for time constraints, Rom skipped most of it.) The third part described Rom’s daring Program for proving Erdos distance one conjecture. (It is too late now, since the conjecture was refuted 🙂 ; Seriously, it could still be useful if you want to prove the conjecture for, say, points in \mathbb Q [\sqrt 3]^2.

 

Posted in Combinatorics, Conferences, Convex polytopes, Geometry | Tagged | Leave a comment

The Ramanujan Challenge for AI

Posted on July 2, 2026 by Gil Kalai

The Ramanujan challenge

Ido Kaminer shared with me the following information  about The Ramanujan Challenge for AI, and I am happy to share it with the readers of this blog. The challenge page is at  ramanujanmachine.com/ramanujan-challenge; Here is the The full challenge paper, and a quote from Ido’s email.

“The challenge launched today and will run until August 1, 2026. It consists of [ten] research-level problems on explicit formulas for mathematical constants, designed to test whether AI systems can move from a concrete formula to a valid proof or symbolic derivation.

We designed the rules to make the challenge compatible with formal and code-based systems. Accepted submissions may be formal proofs, CAS-based derivations, or human-readable proofs accompanied by reproducible code. The goal is not only to test whether AI can find answers, but whether it can produce derivations that can be checked in a structured way.”

 

The second problem

Posted in AI, Combinatorics, Number theory | Tagged , | 2 Comments

Matching in NC and Local Events

Posted on June 22, 2026 by Gil Kalai

Matching is in NC

Matching theory is one of the richest gold mines of ideas and results in mathematics, computer science, and beyond. Recently, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, and Thomas Thierauf proved that bipartite matching is in NC. Namely, there is an algorithm with a polynomial number of processors and polylogarithmic depth that decides whether a bipartite graph has a perfect matching. This problem has long been regarded as a holy grail of complexity theory. Congratulations to Abhranil, Sumanta, Rohit, Roshan, and Thomas.

The authors write in the abstract that “the techniques are based on the polynomial method, inspired by a construction of subspace designs by Guruswami and Kopparty (Combinatorica, 2016).”

(See also this post about matching theory and VVV.)

A remaining open problems is whether the result extends to finding perfect matching in general (non bipartite) graphs.

The search problem of finding (in NC) a perfect matching in bipartite graphs is known to follow from the decision problems; see Vijay Vazirani’s comments below and the paper by Nima Anari and Vijay Vazirani from 2019, as well as Rohit Gurjar’s comment and the 2016 paper by  Fenner, Gurjar, and Thierauf. 

Local Mathematical Events

Birthdays

There is a great deal of mathematical activity around (sometimes with conflicting schedules), but not many international visitors.

Last week there was a week-long school (Midrasha) on “Groups, expanders, and codes,” marking Alex Lubotzky’s 70th birthday. (See this post for my after-dinner speech for Alex ten years ago.)

Two weeks ago there was a lovely one-day conference celebrating Yaron Ostrover’s 50th birthday, where I gave a talk on the 3^d conjecture. (See this post.)

Noga Alon and I are organizing a session celebrating Micha Perles’ 90th birthday, featuring, besides the two of us, Nati Linial, Ron Adin, and Rom Pinchasi. It will take place on July 6 and will be part of the two-day meeting of the Israel Mathematical Union at Bar-Ilan University on July 5-6. On July 7 there will be our traditional students talk day.

The Israel Academy is devoting an evening to mark Hillel Furstenberg’s 90th birthday. It will take place on July 8.

AI + Math event at TAU

The mathematics department at TAU organized a special day devoted to AI and mathematics, featuring Ronen Eldan (OpenAI and the Weizmann Institute) as the main speaker.

Itai Benjamini organized one of the discussion groups on AI and mathematical research and kindly invited me to participate. It was very interesting.

Yonatan Aumann on the centipede game

Yonatan Aumann gave a beautiful lecture presenting an approach, developed jointly with his father Robert Aumann, for dealing with the centipede game. The occasion was a one-day workshop “Games, Rationality and Society” marking the 20th anniversary of Robert Aumann’s Nobel Prize, which included many other lovely lectures.

Last week, many friends of mine participated in a conference in Paris “Half a Century of Agreeing to Disagree” celebrating the 50th anniversary of Aumann’s celebrated agreement theorem.

Kazhdan’s Hypercontractivity and Groups Seminar

Our Kazhdan’s seminar on hypercontractivity and representation theory is approaching its final weeks. After a few introductory lectures, most of the talks were given by Noam Lifshitz and were devoted to hypercontractivity and group representations.

I gave two lectures in which I summarized some early applications of hypercontractivity in other directions and discussed several open problems. Had we had more time, we could also have discussed additional applications of hypercontractivity to global functions, and I may add some material on this topic to the course webpage. Nati Linial is a dominant participant in the seminar and asked some great questions about representation theory that led to wonderful micro-lectures by David.

Top row: Old friends celebrating Yael and Arnon’s wedding; David taking the chalk to give a one-minute introduction to étale cohomology, at Nati’s request. Middle row: RUNI’s new robot; Eden Ben-Zaken performing at RUNI; bottom row: Shira Tanny lecturing at Yaron Ostrover’s day; Ronen Eldan lecturing about things mathematicians should know about LLMs.

 

 

 

Posted in Combinatorics, Computer Science and Optimization, Conferences, Updates | 9 Comments

A sensational Ramsey breakthrough by Domagoj Bradač (reblogged from Sam Mattheus’ blog)

Posted on June 18, 2026 by Gil Kalai
A sensational Ramsey breakthrough by Domagoj Bradač

Gil’s comment: A great result and a beautiful blog post about it. (I thank Nati Linial and Yuval Wigderson who told me about it.) Here is a blog post about the breakthrough on computational complexity.

Posted in Combinatorics, Updates | Tagged | Leave a comment

Three Interviews

Posted on June 6, 2026 by Gil Kalai

My interview in the Israeli Academy interview series

Interviewer: Alex Lubotzky

Top two pictures, taken from the video. Right: my parents with my sister and me, around 1958. Left: Micha Perles carefully checking the proof of my main thesis result and writing out every step. At the end he triumphantly added “QED!!!” and “תושלב״ע”.

At the beginning of the interview, I mentioned two lessons from my father. One was the formula for ((a+b)^2), which he showed me at a young age; the other was that everything becomes interesting if you devote yourself to it. (These two lessons were included in a short “promo” for the interview prepared by the Academy.)

We spoke about my mathematical activities in high school, where Alex and I first met, and about my years as a research student of Micha A. Perles, alongside a remarkable group of fellow students. We also talked about my wife Mazi—the best choice of my life—and about our children, Neta, Hagai, and Lior, as well as life in Jerusalem and Boston in the 1980s. Mazi and I first met in 1979 on a student trip to Sinai, just a week before it was returned to Egypt.

 

Most of the interview was devoted to mathematics: convex sets and polytopes, Helly-type theorems, high-dimensional trees, the Borsuk conjecture, linear programming, influences, the KKL theorem, noise, and quantum computing. I even brought along some polytopes and solids of constant width for demonstration.

Alex recalled that after my 2018 ICM plenary lecture he jokingly told me that my lecture had caused stock markets around the world to fall. I responded that Google’s flawed 2019 “quantum supremacy” announcement arguably caused investors in Bitcoin to lose ten billion dollars or so. We also briefly discussed the free-will problem in the context of the inherent noise sensitivity of physical systems.

At the end, we reminisced about two trips we took together: one in the 1970s to the Jordan River, and another in 2004, with our wives Yardena and Mazi, to the Amazon River and Rio.

Bottom two pictures, taken during the interview. Right: with Alex Lubotzky and Yael Ben Haim. Left: with a few of my favorite polytopes.

My interview in ECAA.

Interviewer: Toufik Mansour

Toufic Mansour founded the journal Enumerative Combinatorics and applications, and has conducted an impressive series of interviews with combinatorialists (and mathematicians with interests in combinatorics). Here is Toufik’s 2022 interview with me.

Some of Toufik’s questions are common to all his interviews, while others were specific to my research. If I ever decide to write a scientific autobiography, this interview could serve as a starting point.

Toufik asked about my formative years, and I told him about a book I received from my mother.

Mansour: We would like to ask you about your formative years. What were your early experiences with mathematics? Did these come under the influence of your family or other people?

Kalai: “… My mother gave me her high-school calculus book (she did not like mathematics very much, but realized that I did), and I remember trying to read it. I could understand various things (like functions), but I got stuck on the expression f(x+\Delta)-f(x). I knew that x was a variable representing numbers, but I did not understand how numbers could be added to triangles.”

Toufik also asked about problems I have worked on for many years, and I mentioned three of my own: the cascade conjecture from 1974, the influence-entropy conjecture, and the following problem from the 1980s: find a (weighted) enumeration of Laman graphs with n labeled vertices that gives {n \choose 2}^{n-3}.

Toufik asked me if there are there are topics in mathematics that are more important than others. I answered that I suppose there are such topics but then concluded with the statement  “I am not sure if importance is that important.” Looking back, sometimes this remark strikes me as clever, and at other times as rather silly.

My interview in the “Superposition Guy”

Interviewer: Yuval Boger

Yuval Boger interviewed me on his podcast.  Transcript; Spotify.

Yuval Boger asked excellent questions about my position on quantum computing, and I was quite pleased with the substance of my answers. As for my delivery and English, at times I was reminded of what one of my MIT students in Calculus 18.011 wrote about me in 1983: “The TA mumbles, fumbles, and bumbles.” (In that course, taught by the legendary Frank Morgan, Noga Alon, Paul Seymour, and I were among the TAs.)

Toward the end, Yuval asked what I hoped the quantum computing community would take from my work, regardless of who ultimately turns out to be right.

In my response, I mainly elaborated on what might be learned from my work if I am right and, as I expect, scalable quantum computing—and even significant early milestones toward it—cannot be achieved. Such a possibility could have implications beyond quantum computing itself and may shed light on several questions in physics. I mentioned, for example, the scope of the time-energy uncertainty principle and the question of whether the new phases of matter required for topological quantum computing (“Majorana zero modes”) can actually exist.

At the same time, I said that if I am correct about quantum computers, then a great deal of the effort invested in this area will ultimately reach a dead end. In this context, I expressed my enthusiasm for the many smaller problems that arise within this grand endeavor, and my broader view that what we do has value—scientifically, intellectually, and personally—even if things do not go our way or according to our hopes.

This applies to many efforts toward quantum computing, which would become considerably less important if my theory is correct. It also applies more broadly to the work of mathematicians and scientists in a future where AI may be able to replace some of us.

Posted in Academics, Applied mathematics, Combinatorics, Convex polytopes, Open problems, Philosophy, Quantum | 1 Comment

Amazing: Erdős’ Unit Distance Problem was Disproved! It was achieved by AI!

Posted on May 21, 2026 by Gil Kalai

Paul Erdős’s, in his 1946  paper published in the American Mathematical Monthly, posed two general questions about the distribution of distances determined by a finite set of points in a metric space.

1. Unit Distance Problem: At most how many times can the same distance (say, distance 1) occur among a set of n points?

2. Distinct Distances Problem: What is the minimum number of distinct distances determined by a set of n points?

Erdős conjectured that in the plane the number of unit distances determined by n points is at most n^{1+c/loglog n}, for a positive constant c, but the best known upper bound, due to Spencer, Szemeredi, and Trotter is only O(n^{4/3}).

As for the Distinct Distances Problem, the order of magnitude of the conjectured minimum is n/\sqrt{log n}.  In 2010 a sensational paper of Guth and Katz presents a proof of an almost tight lower bound of the order of n/log n. Janos Pach wrote about it in this 2010 post. See also this post from 2008, that explains (among other things) the proof for the upper bound.

I have just learned that an internal model of OpenAI have very recently disproved Erdős’ conjecture for the unit distance problem and found an example with more than n^{1+\epsilon} unit distances. This is truly amazing. The construction relies on algebraic number theory.

Here is Open AI announcement and technical paper.

The proof is presented, explained and discussed in the paper Remarks on the disproof of the unit distance conjecture by Alon, Bloom, Gowers, Litt, Sawin, Shankar,Tsimerman, Wang, and Matchett Wood. (I learned about it from an answer to an MO question on the topic of mathematics and AI.)

Like the computer-based proof of the four color theorem in 1976 by Appel and Haken, this may well be a scientific landmark whose importance goes beyond combinatorics and beyond mathematics. I will add a link to the Open AI document when I will have it. (Done.)

There is also a short Open AI video where the result is presented by Tim Gowers and by four members of the team, Lijie Chen, Mark Sellke, Mehtaab Sawhney, and Sebastien (Seb) Bubeck.

Updates: Will Sawin proved a lower bound of n^{1.014}; This was further improved to n^{1.0318}; There are interesting comments on the ErdosProblems site; The list of best constants so far can be found in Terence Tao’s Github. Sawin also proved in the same paper a limit 1.2143 for the new method.

The result is reported and discussed on the Geomblog, computational complexity, and Shtetl Optimized; There is an interesting commentary by Erik Hoel. Following the OpenAI result, Anthropic reported being able to autonomously disprove the unit-distance conjecture (in its strongest form) with its system. Inspired by the disproof of Erdős’ unit distance conjecture, Thomas Bloom, Will Sawin, Carl Schildkraut, and Dmitrii Zhelezov disproved Erdős-Szemeredi Sum-Product Conjecture (over the reals). (See the 2008 post mentioned above for the statement and connection.) Cosmin Pohoata whote a detailed beautiful post (on the sum-product breakthrough) his result inspired by these two breakthroughs: a disproof of the Elekes–Rónyai problem.   Thomas Bloom wrote a detailed beautiful blog post about the developments. Here is an interesting videotaped lecture of Noga Alon. 

Remarks (about the problem): For an approach to improve the upper bound for the problem see the paper Erdős’s unit distance problem and rigidity, by János Pach, Orit E. Raz, József Solymosi  (2025). We discussed a lecture by Orit Raz on the topic in this post. Other posts (in “Combinatorics and more”) related to the Erdos distance problem and to related problems are listed in this comment.

Remarks (About the AI+math): This breakthrough adds to several others remarkable applications of AI to Math. See for example this post over Terry Tao’s blog on Erdős problem 1196 which was settled by Open AI model a few weeks ago. Very recently, a team at DeepMind  used their model to solve several open problems and their proofs come with Lean verification.  From ancient times (January 2026) let me mention an interesting blog post Problem 728 and the use of AI on Erdős problems, by Kevin Baretto. (June 3, 2026) There is an interesting Leiden Declaration on Artificial Intelligence and Mathematics.

Closer to me personally: Ori Gurel-Gurevich, Asaf Nachmias, and Sushant Sachdeva used an internal model of OpenAI to settle a problem about electrical flow in graphs; (I just met Asaf a few days ago in a special Day of Tel-Aviv University devoted to AI and Math.) Pablo Soberón used  LLM-based tools in the brainstorming stage of a recent truly remarkable paper: Tverberg cores and Kalai’s cascade conjecture.

Posted in AI, Combinatorics, Geometry, Updates, What is Mathematics | Tagged , , | 34 Comments

Polymath Plus AI

Posted on April 3, 2026 by Gil Kalai

This post was written together with Nissan Hajaj and Ido Kaminer. 

Update (June 26,2026):  The problem for the first project has now been resolved. 
Update (June, 26, 2926): For all projects (currently four) see our project page.

Update (April 5, 2026): The first project is launched here.

AI and Math has become a hot topic (and a source of some worries) among and beyond the mathematical community.

Nissan Hajaj from Google Research proposed to run an “AI polymath project” based on a similar concept of polymath project but with participation of AI agents. Together with Ido Kaminer we decided to run a pilot experiment with a couple of projects.

Nissan’s vision for the AI-polymath project

By empowering collaborative research initiatives with AI tools, we can create a powerful platform that applies the scientific potential of modern AI to the most advanced frontiers of active research. Projects like Polymath demonstrate how the mathematical community has already embraced collective efforts; such models can now be enhanced by the evolving capabilities of AI to accelerate research progress while offering developers a space to refine these tools through real-world academic interaction.

We envision an open, hybrid research ecosystem where human experts and AI agents collaborate seamlessly, utilizing shared tools and resources as needed. In this environment, both human participants and AI entities can engage in ongoing dialogues, offering insights, solutions, and critiques. Our proposal focuses on establishing a platform designed to initiate,oversee, and complement these specialized mathematical research communities, featuring:

  1. Dedicated AI utilities for community administration, including workflows, literature analysis, documentation, review, verification, and planning.

  2. Frameworks designed for registering, deploying, and coordinating AI tools made available to the community.

  3. A transparent interface that invites contributions from both human researchers and automated agents.

Our objective is to select a diverse array of mathematical problems spanning various subfields, each presenting unique hurdles for both human intellect and AI-driven methodologies.

What we plan to do

We would like to have a preliminary (and rather partial) implementation of Nissan’s idea: To start with a description of a project (polymath X) and to proceed with AI contributions on the comment section.

The (default) prompt:

Polymath X with the participation of AI agents is dealing with the following mathematical problem:
—Short Formulation—-
An introduction to the project and the discussion so far can be found in this LINK.[Note: The link itself will change according to the project. Here are a few links for projects that are potentially relevant: 1) This MO problem; 2) A combinatorial abstraction of the “polynomial Hirsh conjecture”; 3) The first proposal in this post; 4) Some of the proposals from this MO question.) ]
Please make a comment, preferably limited to 3-4 paragraphs. (If you have more to say, contribute several comments.)
Your comment may include (but are not limited to) one or more of the following
  1. A new idea for the project,
  2.  Some further thoughts on current ideas,
  3.  A comment on some earlier comments,
  4.  Proofs, heuristic arguments, examples, counter-examples, and conjectures,
  5.  Computer-programs and computer experimentation.

The comment section of the present post can serve for “meta discussion” for this project. 

In addition of a general discussion of the idea we can think about specific projects to run.

Potential stages and specific tools

Nissan sees several possible stages for the project. For example:

  1. Manually setting up the Polymath site/post and inviting participants.
    Every AI participant will need to find a way to interact with the site (through comments).
  2. Manually setting up the Polymath site/post and inviting participants—both humans (through comments) and agentic participants (through a published API).  
  3. A semi-automatically managed site, where content generation, reviews, and moderation can be facilitated by AI.
  4. The same as (3), but with additional special-purpose AI tools and resources dedicated to the effort.

In the long term, Nissan envisions such an effort evolving into a collection of encyclopedic entries (similar to Wikipedia) that are maintained and advanced by the hybrid community, with dedicated computational resources to explore solutions autonomously.

(Our blog efforts will be limited to items 1 and 2. API stands for Application Programming Interface.)

A few words about Ido

In addition to his research in experimental physics, Ido Kaminer and his collaborators developed in 2021 the Ramanujan Machine which is “a novel way to do mathematics by harnessing your computer power to make new discoveries. The Ramanujan Machine already discovered dozens of new conjectures.” We mentioned the Ramanujan Machine in this 2021 post. His group expanded this idea to build a library of connections among mathematical constants (ICLR 2025) and unify their formulas (NeurIPS 2025). We mentioned the Ramanujan Machine in this 2021 post. More recently, the research of his group expanded also to computations in physics. See Ido’s videotaped lecture From π to QFT: Symbolic Discovery at Scale.

Other Polymath news

On some other polymath news, Tim Gowers recently proposed a polymath project about the word problem in the Artin-Tits group.

AI+Math

On the topic of AI+Math (and math of CS), let me mention that I also had very pleasant and thought-provoking discussions with Rafi Ostrovsky and Yuval Rabani.

I also had  some illuminating correspondence with Dr. Z. (Separate to his pioneering and provocative role in Math+AI, see Doron’s surprise proposal from yesterday.)

Posted in AI, Mathematics and Computers, Mathematics over the Internet, Open discussion, Polymath projects | Tagged , , , , , | 6 Comments