2023-2024 Seminars

A graph $G$ is said to be Ramsey for a tuple of graphs ($H_1,...,H_r$) if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$, for some $i$. A fundamental question at the intersection of Ramsey theory and the...

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

Subsets $A$ of an abelian group with a small doubling $|A+A|/|A|$ have been extensively studied, and results of Freiman, Ruzsa and Green give fundamental structural descriptions of such sets. These have important applications across combinatorics...

In a $3$-$\mathsf{XOR}$ game $\mathcal{G}$, the verifier samples a challenge $(x,y,z)\sim \mu$ where $\mu$ is a probability distribution over $\Sigma\times\Gamma\times\Phi$,  and a map $t\colon \Sigma\times\Gamma\times\Phi\to\mathcal{A}$ for a...

A sparsification of a structure, with respect to a class of queries, produces a compressed representation of the structure while answering every query in the class approximately correctly. The seminal example of sparsification is "graph...

The method of hypergraph containers is a widely-applicable technique in probabilistic combinatorics. The method enables one to gain control over the independent sets of many `interesting' hypergraphs by exploiting the fact that these sets exhibit a...