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

#
Computer Science and Discrete Mathematics (CSDM)

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