2025-2026 Seminars

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 $x_1,\dots,x_n$ to simultaneously send messages to an evaluator, so that the messages are received in a random...

A common tool in the construction of probabilistically checkable proofs is low degree encodings. Babai, Fortnow and Lund proved the local testability of the individual low degree code, and used it to provide a multi-prover interactive proof (MIP)...

Suppose we have some system X, that evolves over time. We want to communicate the status of a point in X at all times using a bandwidth limited channel. How big a bandwidth is needed to achieve this? And what is the connection to Shannon entropy and...