New Frontiers in Combinatorics & Computer Science (2025)

Nima Anari
Stanford University

Sampling via Autospeculation
View Slides (PDF)

Sampling from a distribution and counting (computing certain statistics or partition functions) are related tasks that are equivalent under polynomial-time reductions for many distributions of interest. The naive reductions are inherently sequential. Nima Anari will talk about parallelizing sampling via counting. We show that surprising polynomial speedups are possible for sampling from *almost arbitrary* distributions in two settings: distributions on [q]^n with access to their conditional marginals (as in any-order autoregressive models) and distributions on R^n accessed by a denoising diffusion oracle (as in diffusion models).
 

Nikhil Bansal
University of Michigan

On Beck-Fiala and Komlós Conjectures
View Slides (PDF)

A conjecture of Komlós states that the discrepancy of any collection of unit vectors is \(O(1)\).

More formally, for any matrix A with unit columns, there is a vector \(x \in {-1,1}^n\) such that \(|Ax|_\infty = O(1)\). The related Beck-Fiala conjecture states that the discrepancy of any set system with maximum degree k is O(k^{1/2}).

Nihkil Bansal will describe an \(O(log^{1/4}n)\) bound for the Komlós problem, improving upon the \(O(log^{1/2} n)\) bound due to Banaszczyk. We will also see how these ideas can be used to resolve the Beck-Fiala conjecture for \(k >> log^2n\).

This is based on joint work with Haotian Jiang.
 

Jacob Fox
Stanford University

Independence in Random Graphs

Various random graphs models satisfy that each edge appears independently of all other edges but those in a bounded degree graph. Examples include Erdős–Rényi random graphs, random Cayley graphs, random Latin square graphs, and random entangled graphs. We begin the systematic study of random graphs under this weak independence hypothesis, focusing on the clique number. We prove optimal bounds when each edge appears with the same constant edge density. The lower bound is tight for the Erdős–Rényi random graph, and the upper bound is tight for random Cayley graphs in abelian groups of bounded torsion. The upper bound solves various open problems in the area. We will also discuss the solution of conjectures of Ruzsa on quantitative versions of Freiman’s theorem and of Alon and Orlitsky in information theory building on the same methods. Time permitting, we will discuss other graph properties that hold for such general graph models. Based on joint works with David Conlon, Huy Tuan Pham, and Liana Yepremyan.
 

Venkatesan Guruswami
University of California, Berkeley

CSP Non-Redundancy: Exploring a Rich Landscape Across Sparsification, Algebra, and Combinatorics
View Slides (PDF)

Constraint satisfaction problems (CSPs) provide a unifying framework for capturing a wide array of computational problems. A basic notion in this landscape is that of redundancy: a constraint is redundant if it is logically implied by the rest. The study of non-redundancy—instances where no constraint is redundant—has recently emerged as a powerful lens for understanding core questions in sparsification, extremal combinatorics, and universal algebra.

In this talk, Venkatesan Guruswami will describe a recent line of work that systematically develops the theory of CSP non-redundancy. A central result (with J. Brakensiek, STOC 2025) shows that the sparsifiability of any CSP is determined—up to polylogarithmic factors—by its non-redundancy. Our sparsification theorem is established in the very general context of set families, and it unifies and generalizes known sparsification results for graph cuts, linear codes, and various CSP classes. The proof involves a novel application of the entropy method, inspired by Gilmer’s recent breakthrough on the union-closed sets conjecture.

In follow-up work (with J. Brakensiek, B. Jansen, V. Lagerkvist, and M. Wahlström, arXiv:2507.07942), we construct explicit CSP predicates whose non-redundancy scales as Θ(n^r) for every rational r ≥ 1, revealing a rich and previously unanticipated spectrum. We also develop an algebraic theory of conditional non-redundancy via pattern polymorphisms, drawing connections to Turán-type extremal problems in graphs and hypergraphs. Further extending this theory, we revisit the notion of Mal’tsev embeddings—the most general known technique for proving linear non-redundancy. Introducing a new tool, Catalan polymorphisms, we resolve several structural questions about Mal’tsev embeddings, including the construction of a predicate whose embedding arises not from an Abelian group, but from the quantum Pauli group.
 

Zander Kelley
Institute for Advanced Study

A More Efficient Sifting Lemma and a Stronger 3-Player Communication Lower Bound

A central goal in complexity theory is to prove separations between randomized and deterministic models of computation. In communication complexity, a key challenge is to establish lower bounds for multiparty protocols in the number-on-forehead model. Recent work by Kelley, Lovett, and Meka provided a separation for an explicit 3-player function, proving a deterministic lower bound of \(Ω(log^{1/3}(N))\) for a function with a constant-cost randomized protocol.

The proof of this lower bound involved showing that the ‘yes’ instances of a function cannot be efficiently covered by cylinder intersections. This analysis hinges on a sifting lemma for bipartite graphs, which guarantees that any graph with a large ‘grid norm’ must contain a smaller, much denser induced subgraph. In this talk, based on joint work with Xin Lyu, Zander Kelley will present a new, more efficient version of this sifting lemma. This strengthening of the core technical tool allows us to improve the 3-player lower bound to \(Ω(log^{1/2}(N))\), achieving a stronger separation.
 

Subhash Khot
New York University

Approximating Satisfiable CSPs, Additive Combinatorics, Parallel Repetition, and More

Hastad showed that 3SAT has a sharp approximation threshold of 7/8 on satisfiable instances. Specifically, given a satisfiable instance of 3SAT, one can algorithmically find an assignment that satisfies 7/8 fraction of the clauses and it is NP-hard to do strictly better.

This talk will give an overview of our continued effort towards characterizing such a sharp threshold for every satisfiable constraint satisfaction problem (CSP). Our results so far include: a hybrid algorithm that combines semi-definite programming and Gaussian elimination over an Abelian group and is (arguably) optimal for some CSPs; progress on some questions in additive combinatorics, in particular, the Density Hales-Jewett theorem; progress on the 3-player parallel repetition theorem; and progress on some questions in property testing.

At the heart of these results lies progress on an analytic question, namely, understanding expectations of the type E [f(x) f(y) f(z)] where x,y,z are correlated inputs from a product space and f is a bounded function.

Based on joint works, mostly with Amey Bhangale, Dor Minzer, Yang P. Liu, and some with Mark Braverman and Kunal Mittal.
 

Pravesh Kothari
Princeton University

TBA
 

Shachar Lovett
University of California, San Diego

Adaptive Random Restrictions

Random restrictions are a powerful tool in complexity theory with many applications. We develop a new *adaptive* random restriction process, which takes into account how a target complexity measure changes during the restriction process. We then use it to derive new results in boolean function analysis.

Nisan and Szegedy proved that for any boolean function, its degree and approximate degree are polynomially related. Using an adaptive random restriction process, we show that the same conclusion holds if one replaces “degree” with “log of sparsity,” and use it to limit the power of randomness for AND decision trees.

Joint work with Arkadev Chattopadhyay and Yogesh Dahiya.
 

Dor Minzer
Massachusetts Institute of Technology

Size Efficient PCPs and Fault-tolerant Routing via HDX
View Slides (PDF)

We will discuss recent PCP constructions based on high-dimensional expanders that achieve small soundness and quasi-linear size, which are two key properties of PCPs. To do so we discuss the idea of ‘derandomized hardness amplification,’ which is a soundness amplifying procedure that only incurs a mild size blow-up, and show how to achieve it (in the context of PCPs) via high-dimensional expanders. No special background will be assumed.

Based on joint works with Mitali Bafna, Noam Lifshitz, Nikhil Vyas, and Zhiwei Yun.
 

Ankur Moitra
Massachusetts Institute of Technology

Phase Transitions in Quantum Spin Systems

Classical spin systems exhibit a variety of interesting phase transitions wherein there are sudden and dramatic changes in their macroscopic behavior as the temperature varies. In this talk, Ankur Moitra will introduce quantum spin systems and study the relationship between entanglement and temperature. In particular, Moitra will show that above a constant temperature, that depends only on the degree and locality of the interactions, there is literally zero entanglement.

While the proof involves some unusual manipulations, Moitra will attempt to explain it through analogies with the classical setting.

This is based on joint work with Ainesh Bakshi, Allen Liu, and Ewin Tang.
 

Shayan Oveis Gharan
University of Washington

C-Lorentzian Polynomials and Applications
View Slides (PDF)

Completely log-concave, a.k.a., Lorentzian, polynomials, were discovered a few years ago where they were used to relate seemingly distant areas of math and computer science, such as the geometry of polynomials, Hodge theory for combinatorial geometries, theory of high dimensional expanders, and mixing time of Markov chains. Consequently, they lead to a resolution of several long-standing open problems on matroids such as the Mason’s log-concavity conjecture and the Mihail-Vazirani conjecture on the expansion of the bases exchange graph.

Unfortunately, this family of polynomials are limited as their support corresponds to bases of a matroid or more generally lattice points of a generalized permutahedra. In this talk, Shayan Oveis Gharan will explain a generalization of Lorentzian polynomial to convex cones in the positive orthant, called C-Lorentzian polynomials, and use them to study combinatorial objects such as distributive, modular, or geometric lattices and the corresponding sampling, and log-concavity problems. Enroute we will also discuss new local-to-global theorems for high-dimensional expanders called trickle-down theorems.

Based on a joint work with Jonathan Leake and Kasper Lindberg.
 

Sarah Peluse
Stanford University

Integer Distance Sets

Sarah Peluse will speak about joint work with Rachel Greenfeld and Marina Iliopoulou in which we address some classical questions concerning the size and structure of integer distance sets. A subset of the Euclidean plane is said to be an integer distance set if the distance between any pair of points in the set is an integer. Our main result is that any integer distance set in the plane has all but a very small number of points lying on a single line or circle. From this, we deduce a near-optimal lower bound on the diameter of any non-collinear integer distance set of size n and a strong upper bound on the size of any integer distance set in [-N,N]^2 with no three points on a line and no four points on a circle.
 

Huy Pham
California Institute of Technology

What Is the Complexity of Sets with Small Doubling?
View Slides (PDF)

Sets with small doubling |A+A|/|A| play a key role in additive combinatorics and computer science. Initiating from the study of random Cayley graphs, we obtain new combinatorial and probabilistic perspectives on sets with small doubling, providing novel ways to quantify their structure and complexity.

In particular, Huy Pham will discuss a combinatorial structural lemma which is the key ingredient in our resolution of Ruzsa’s conjecture on the structure of sets with small doubling and the analysis of dense random Cayley graphs. Pham will also discuss a probabilistic argument to efficiently construct covers for small sumsets, which can be thought of as low-complexity approximations to sets with small doubling.

Joint work with N. Alon, D. Conlon, J. Fox, L. Yepremyan.
 

Mehtaab Sawhney
Columbia University

Quasipolynomial Bounds for the Corners Theorem

We prove quasipolynomial bounds for the corners theorem for general abelian groups. The proof draws on a number of themes in additive combinatorics, including recent work of Kelley-Meka on 3-term arithmetic progressions, work on almost periodicity, and work of Conlon, Fox, and Zhao on densification.

Based on joint work with Michael Jaber, Yang P Liu, Shachar Lovett and Anthony Ostuni.
 

Lisa Sauermann
University of Bonn

Rainbow Cycles in Properly Edge-Colored Graphs
View Slides (PDF)
 

Daniel Spielman
Yale University

Discrepancy Theory and Randomized Controlled Trials: Results and Conjectures

Discrepancy theory tells us that it is possible to divide a set of vectors into two sets that look surprisingly similar to each other. In particular, these sets can be much more similar to each other than those produced by a random division.

The development of discrepancy theory has been motivated by applications in fields including combinatorics, geometry, optimization, and functional analysis. But, we expect its greatest impact will be in the design of randomized controlled trials (RCTs).

This lecture will formalize the connection between discrepancy theory and RCTs and survey our current understanding. The application to RCTs motivates improvements in the bounds we obtain in discrepancy theory, the speed of the algorithms that obtain them, and the contexts in which they can be applied. We’ll discuss what we expect to be true and what we hope might be as well.
 

Madhu Sudan
Harvard University

Eigenvalue Bounds for Markov Chains on Multislices
View Slides (PDF)

Consider the following natural random walk whose states are the balanced vectors of \(\{0,1\}^n\), i.e., the balanced Boolean slice with an equal number of \(0\)s and \(1\)s, where a single step of the random walk takes a state \(u\) to a state \(v\) at Hamming distance exactly \(n/2\) from it. One would expect this random walk to mix extremely rapidly, and indeed this has been known since (at least) the work of Delsarte in 1978.

Now consider the following variant of the above random walk: The states now are elements of the “balanced multislice” in \(\{-1,0,1\}^n\), i.e., vectors with exactly \(1/3\)rd fraction of the letters \(-1\), \(0\) and \(1\), and in a single step from a balanced vector \(u\) to a random balanced vector \(v\) obtained by flipping exactly \(1/3\) fraction of each of the letters of \(u\) to \(-1\), \(0\) and \(1\). (So for a single coordinate \(i\), \(v_i\) is uniform in \(\{-1,0,1\}\) conditioned on \(u_i\).) It is intuitive to believe that such a random walk should also converge to the uniform distribution over all balanced vectors extremely fast, but this seems not to have been known till now.

In this talk, Madhu Sudan will use and convey a limited knowledge of representation theory to show how to prove such a result, specifically, that for every s, the random walk matrix of any *symmetric* walk on the balanced multislice in \(Z_s^{sn}\) that takes *nearly uniform* steps has second eigenvalue \(o_n(1)\), where “symmetric” requires that the random walk is invariant under permutations of \(S_n\), and “nearly uniform” implies that if the walk moves from \(u\) to \(v\) with positive probability that the distribution of \((u_i,v_i)\) for random i is nearly uniform on \(Z_s^2\).

Time permitting, some motivation from some coding-theoretic questions might also be given.

Joint work with Prashanth Amireddy, Amik Raj Behara, and Srikanth Srinivasan.
 

June Vuong
University of California, Berkeley

Generalized Log-Concavity and Algorithmic Applications
View Slides (PDF)

The seminal works of Brändén-Huh (2018) and Anari-Liu-Oveis Gharan-Vinzant (2019) established the connection between the log-concavity (equivalently, Lorentzian-ness) of a matroid’s generating polynomial and the rapid mixing of basis exchange walks. In this talk, June Vuong will introduce several relaxations of log-concavity, namely, fractional log-concavity, spectral independence, and entropic independence, and discuss their implications for sampling and optimization algorithms.

In particular, Vuong will show that the generating polynomial of particle systems from statistical physics satisfies a generalized log-concavity condition at high temperatures, which in turn implies the fast mixing of the associated Glauber dynamics. June will also present a conjecture linking sampling and optimization over 0/1 polytopes, whose resolution would address several open problems in the mixing times of Markov chains and yield new progress on the Mihail-Vazirani conjecture.
 

Avi Wigderson
Institute for Advanced Study

Fun with Symmetric Polynomials (or, Polynomial GCD in Constant Parallel Time)
View Slides (PDF)

We design polynomial size, constant depth (namely, 𝖠𝖢0) arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of the discriminant, resultant, Bézout coefficients, squarefree decomposition, and the inversion of structured matrices like Sylvester and Bézout matrices. Previously, the best known arithmetic formulae for these problems required super-polynomial size, regardless of depth.

These results are based on new algorithmic techniques to compute various symmetric functions in the roots of polynomials, as well as manipulate the multiplicities of these roots, without having access to them. These techniques allow 𝖠𝖢0 computation of a large class of linear and polynomial algebra.

Joint work with Robert Andrews