A common theme in mathematics is that limits of finite objects
are well behaved. This allows one to prove many theorems about
finitely approximable objects, while leaving the general case open
--- examples for this are Gottschalk's conjecture...
It was conjectured by Alon in the 1980s that random d-regular
graphs have the largest possible spectral gap (up to negligible
error) among all d-regular graphs. This conjecture was proved by
Friedman in 2004 in major tour de force. In recent years...
We consider the problem of sorting a set of items having an
unknown total order by doing binary comparisons of the items, given
the outcomes of some pre-existing comparisons. We present a simple
new algorithm with a running time of O(m + n + log T)...
Chernoff's bound states that for any A⊂[N] the probability a
random k-tuple s∈([N]k) correctly `samples' A (i.e. that the
density of A in s is close to its mean) decays exponentially in the
dimension k. In 1987, Ajtai, Komlos, and Szemeredi proved...
In this talk, I'll show that the most natural low-degree test
for polynomials over finite fields is ``robust'' in the high-error
regime for linear-sized fields. This settles a long-standing open
question in the area of low-degree testing, yielding...
A graph G is said to be Ramsey for a tuple of graphs (H1,...,Hr)
if every r-coloring of the edges of G contains a monochromatic copy
of Hi in color i, for some i. A fundamental question at the
intersection of Ramsey theory and the theory of random...
The central problem of physics and quantum chemistry is to find
the ground state energy of some physical system governed by quantum
mechanics. In mathematical terms, this means finding the
lowest eigenvalue of some linear operator on a vector space...
In this talk, we will present a new approach for approximating
large independent sets when the input graph is a one-sided
expander—that is, the uniform random walk matrix of the graph has
second eigenvalue bounded away from 1. Specifically, we show...
A cornerstone result in geometry is the Szemerédi–Trotter
theorem, which gives a sharp bound on the maximum number of
incidences between m points and n lines in the real plane. A
natural generalization of this is to consider
point-hyperplane...
In this talk, I will discuss lower bounds for a certain
set-multilinear restriction of algebraic branching programs. The
significance of the lower bound and the model is underscored by the
recent work of Bhargav, Dwivedi, and Saxena (2023), which...
