Seminars in Extremal Combinatorics

Pravesh Kothari: Sum-of-Squares Proofs, Efficient Algorithms, and Applications

18th March, 2024

Any non-negative univariate polynomial over the reals can be written as a sum of squares. This gives a simple-to-verify certificate of non-negativity of the polynomial. Rooted in Hilbert's 17th problem, there's now more than a century's work that finds the right multivariate generalizations called Positivstellensatz theorems (due to Krivine, Stengle, and Putinar). Beginning in the late 1980s, researchers (initially independent) in optimization, quantum information, and proof complexity theory found an algorithmic counterpart, the sum-of-squares algorithm, of these results. Over the past decade, this algorithmic theory has matured into a powerful tool for designing efficient algorithms for basic problems in algorithm design.

In this talk, I will outline a couple of highlights from these recent developments:

1) Algorithmic Robust Statistics: In the 1960s, Tukey and Huber observed that most statistical estimators are brittle -- they break down with almost no guarantee if the model postulated for data has minor misspecification (say because of 1% outliers). In response, they initiated the field of robust statistics. Over the past five years, a new blueprint, based on the sum-of-squares algorithm, has emerged for efficient robust statistics in high dimensions with new connections to finding efficiently verifiable certificates of concentration and anti-concentration properties of high dimensional probability distributions.

2) The Kikuchi Matrix Method: Finding (or proving that there is none) a solution that satisfies 99% of a given system of k-sparse linear equations (i.e., k non-zero coefficients in each equation) over finite fields is a basic NP-hard problem and thus, unlikely to admit efficient algorithms. In the early 2000s, motivated by whether the hard instances are "pathological", researchers explored whether "semirandom" equations - arbitrary systems with right-hand sides generated uniformly and independently at random - could admit efficient algorithms that output efficiently verifiable certificates of unsatisfiability.

Recently, a restricted class of sum-of-squares proofs was at the heart of efficient algorithms for such semirandom sparse linear equations. Surprisingly, these algorithms have led to new progress in extremal combinatorics and coding theory.

Cosmin Pohoata: The Erdős-Szekeres Problem in Three (and Higher) Dimensions

24th January, 2023

Finding the smallest integer N=ESd(n) such that in every configuration of N points in ℝd in general position there exist n points in convex position is one of the most classical problems in extremal combinatorics, known as the Erdős-Szekeres problem. In 1935, Erdős and Szekeres famously conjectured that ES2(n)=2n−2+1 holds, statement which was nearly confirmed in 2016 by Suk, who showed that ES2(n)=2n+o(n). In higher dimensions, on the other hand, it has been unclear even what kind of asymptotic behaviour to expect from ESd(n), with conflicting predictions arising over the years. In this talk, we will discuss a recent proof that ESd(n)=2o(n) holds for all d≥3. Joint work with Dmitrii Zakharov.

Corrine Yap: A Topological Turán Problem

15th March, 2021

The classical Turán problem asks: given a graph H, how many edges can an n-vertex graph have while containing no isomorphic copy of H? By viewing (k+1)-uniform hypergraphs as k-dimensional simplicial complexes, we can ask a topological version of this, first posed by Nati Linial: given a k-dimensional simplicial complex S, how many facets can an n-vertex k-dimensional simplicial complex have while containing no homeomorphic copy of S? Until recently, little was known for k greater than 2. In this talk, we give an answer for general k using dependent random choice - a method that has produced powerful results in extremal graph theory, additive combinatorics, and Ramsey theory.

Swastik Kopparty: Geometric rank of tensors and the subrank of matrix multiplication

22nd February, 2021

I will talk about a new notion of rank for tensors called geometric rank, and discuss some of its basic properties, as well as its relationship with other well-studied notions of rank like subrank, slice rank and analytic rank. As an application, we will see a proof of tightness of an old bound of Strassen on the subrank of the matrix multiplication tensor.

Peter Keevash: Isoperimetric Stability

14th September, 2020

Understanding approximate minimisers for isoperimetric problems is of fundamental importance in Combinatorics, Analysis and Geometry. We will survey some recent progress on these problems in three settings: the Extremal Combinatorics setting of the discrete cube (joint with Eoin Long), the Additive Combinatorics setting of Cayley digraphs on lattices (joint with Ben Barber, Joshua Erde and Alexander Roberts) and the Discrete Analysis setting of Boolean functions with small influence, with applications to sharp thresholds and Extremal Combinatorics via the Junta Method (joint with Noam Lifshitz, Eoin Long and Dor Minzer).

Federico Vigolo: Asymptotic expander graphs

17th July, 2020

A sequence of expanders is a family of finite graphs that are sparse yet highly connected. Such families of graphs are fundamental object that found a wealth of applications throughout mathematics and computer science. This talk is centred around an 'asymptotic' weakening of the notion of expansion. The original motivation for this asymptotic notion comes from the study of operator algebras associated with metric spaces. Further motivation comes from some recent works which established a connection between asymptotic expansion and strongly ergodic actions. I will give a non-technical introduction to this topic, highlighting the relations with usual expanders and group actions.

Eyal Lubetzky: Random Walks on Ramanujan Graphs, Digraphs and Complexes

1st February, 2017

We will discuss the sharp transition in the time it takes simple random walk on regular Ramanujan graphs to approach the uniform distribution (known as the cutoff phenomenon), and geometric consequences (such as typical distances between vertices) that this implies for such graphs. We will then discuss how these ideas can be extended to regular Ramanujan digraphs, and consequently, to any d-dimensional Ramanujan complexes for d > 1 associated with a simple group, with analogous geometric implications for these objects.

Adam Marcus: Two Existence Proofs of Ramanujan Graphs

30th January, 2017

This talk will review two different results regarding the existence of Ramanujan graphs. While both methods employ the method of interlacing polynomials, they are thematically quite different. The goal will be to highlight some of the commonalities and differences.

Will Sawin: Ramanujan Covers

30th January, 2017

The breakthrough work of Marcus, Spielman, and Srivastava showed that every bipartite Ramanujan graph has a bipartite Ramanujan double cover. Chris Hall, Doron Puder, and I generalized this to covers of arbitrary degree. I will explain the proof, with emphasis on how group theory and representation theory are useful for this problem.

Eshan Chattopadhyay: Explicit Constructions of Two-Source Extractors and Ramsey Graphs

30th January, 2017

Randomness is widely used in various areas of computer science, and many of the applications require uniform, uncorrelated bit. However, most sources of randomness in nature are defective and at best, only contain some amount of entropy. This leads to the area of randomness extraction, where an extractor is a deterministic procedure to produce pure random bits from a weak source. A central open problem (from the 80s) in this area is to extract from 2 independent weak sources (it is known that it is impossible to extract from just 1 weak source). In joint work with David Zuckerman, we resolve this problem. I will discuss the main ideas we use to solve this problem.

As a corollary of our 2-source extractor, we obtain exponential improvements in explicit constructions of Ramsey graphs, a central object in extremal combinatorics. This is in a line of work spanning the last 70 years in an attempt to meet Erdős's challenge of matching the probabilistic method.

Daniel Spielman: Ramanujan graphs of every degree

6th November, 2014

We explain what Ramanujan graphs are, and prove that there exist infinite families of bipartite Ramanujan graphs of every degree. Our proof follows a plan suggested by Bilu and Linial, and exploits a proof of a conjecture of theirs about lifts of graphs. Our proof of their conjecture applies the method of interlacing families of polynomials to Mixed Characteristic Polynomials. A bound on the roots of these polynomials will follow from a bound of Heilmann and Lieb on the roots of the matching polynomials of graphs. We also prove that there exist infinite families of irregular bipartite Ramanujan graphs.

Daniel Spielman: Sparsification of graphs and matrices

3rd November, 2014

Random graphs and expander graphs can be viewed as sparse approximations of complete graphs, with Ramanujan expanders providing the best possible approximations. We formalize this notion of approximation and ask how well an arbitrary graph can be approximated by a sparse graph. We prove that every graph can be approximated by a sparse graph almost as well as the complete graphs are approximated by the Ramanujan expanders: our approximations employ at most twice as many edges to achieve the same approximation factor. Our algorithms follow from the solution of a problem in linear algebra. Given an expression for a rank-n symmetric matrix A as a sum of rank-1 symmetric matrices, we show that A can be well approximated by a weighted sum of only O(n) of those rank-1 matrices.