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...
Edit distance is a similarity measure for strings that counts
how many characters have to be deleted, inserted or substituted in
one string to get another one. It has many applications from
comparing DNA sequences to text processing. We are still in...
Where are the hard problems? In the absence of a proof of P ≠
NP, researchers have spent years proving unconditional lower bounds
for constrained models of computation. In time, a distinct theme
arose: random problems (in particular random...
Given two univariate polynomials, how does one compute their
greatest common divisor (GCD)? This problem can be solved in
polynomial time using the Euclidean algorithm, and even in
quasi-linear time using a fast variant of the Euclidean
algorithm...
