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...
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 and...
In a 3-𝖷𝖮𝖱 game , the verifier samples a challenge (x,y,z)∼μ
where μ is a probability distribution over Σ×Γ×Φ, and a map
t:Σ×Γ×Φ→ for a finite Abelian group defining a constraint.
The verifier sends the questions x, y and z to the
players...
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...
