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...
Cayley graphs provide interesting bridges between graph theory,
additive combinatorics and group theory. Fixing an ambient finite
group, random Cayley graphs are constructed by choosing a
generating set at random. These graphs reflect interesting...
