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...
About 20 years ago, Gurvits developed the notion of polynomial
capacity to give a simple proof of the famous van der Waerden lower
bound on the permanent of a doubly stochastic matrix. Since then,
similar techniques have led to various other...
Agreement testing (aka direct product testing), checks if
consistent local information reveals global structure. Beyond its
theoretical connections to probabilistic checkable proofs (PCPs),
constructing agreement testers is a fundamental...
A dictionary data structure maintains a set of at most n� keys
from the universe [U][�] under key insertions and deletions, such
that given a query x∈[U]�∈[�], it returns if x� is in the set. Some
variants also store values associated to the keys...
Endow the edges of the ZD lattice with positive weights, sampled
independently from a suitable distribution (e.g., uniformly
distributed on [a,b] for some b greater than a greater than 0). We
wish to study the geometric properties of the resulting...
