2023-2024 Seminars

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\in[U]$, it returns if $x$ is in the set. Some variants also store values associated to the keys...

Endow the edges of the $Z^D$ lattice with positive weights, sampled independently from a suitable distribution (e.g., uniformly distributed on [a,b] for some b>a>0). We wish to study the geometric properties of the resulting network, focusing on the...

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

A finite set $F$ in $\mathbb{Z}^d$ is a translational tile of  $\mathbb{Z}^d$ if one can cover  $\mathbb{Z}^d$ by translated copies of $F$ without any overlaps, i.e., there exists a translational tiling of $\mathbb{Z}^d$ by $F$.  Suppose that $F$ is...

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