Since their inception, random graphs have been a central topic
in probability and combinatorics, offering a remarkably rich
landscape for studying how complex structures emerge from
randomness. We will discuss the following fundamental
questions...
The van der Waerden number w(k;r) is the minimum positive
integer N such that every r-coloring of the positive integers up to
N contains a monochromatic k-term arithmetic progression.
Estimating these numbers has remained a challenging open
problem...
The first construction of Ramanujan graphs is due to Lubotzky,
Phillips, and Sarnak (STOC 1986, Combinatorica 1987). Their
construction and analysis were deeply algebraic, and at the time it
seemed that only algebraic methods were strong enough to...
The random geometric graph Geo_d(n,p) is a probability
distribution over graphs, constructed by placing n points uniformly
on a d-dimensional sphere and connecting two points whenever they
are sufficiently close — where the proximity threshold is...
By combining sparse graphs with local constraints, expander
codes offer a powerful framework for achieving fast decoding
algorithms while maintaining asymptotically good rate and minimum
distance. However, the standard constraint-counting
arguments...
In the noisy $k$-XOR problem, one is given $y \in
\bF_2^\constraints$ and must distinguish between $y$ uniform and $y
= A x + e$, where $A$ is the adjacency matrix of a $k$-left-regular
bipartite graph with variables and constraints, $x\in \bF_2^...
How does the choice of training data influence an AI model? This
question is of central importance to interpretability, privacy, and
basic science. At its core is the data deletion problem:
after a reasonable amount of precomputation, quickly...
I will describe recent breakthrough results in multiclass PAC
learning that characterize the optimal sample complexity. The talk
will discuss recent work of Chirag Pabbaraju, as well as work of
Steve Hanneke, Qinglin Meng, Shay Moran, and Amirreza...
This talk will be a series of vignettes in topological
combinatorics, centering around lower bounds on the chromatic
number of graphs. The Kneser graph KG(n,k) has as vertices the
size-k subsets of {1,...,n}, with an edge placed between any
two...
The shuffle model is a widely used abstraction for
non-interactive anonymous communication. It allows n parties
holding private inputs x1,…,xn to simultaneously send messages to
an evaluator, so that the messages are received in a random order.
The...
