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