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...
Any non-negative univariate polynomial over the reals can be
written as a sum of squares. This gives a simple-to-verify
certificate of non-negativity of the polynomial. Rooted in
Hilbert's 17th problem, there's now more than a century's work
that...
In distributed certification, our goal is to certify that a
network has a certain desired property, e.g., the network is
connected, or the internal states of its nodes encode a valid
spanning tree of the network. To this end, a prover
generates...
In this talk, we will show that the supremum of any centered
Gaussian process can be approximated to any arbitrary accuracy by a
finite dimensional Gaussian process where the dimension of the
approximator is just dependent on the target error. As a...