Seminars Sorted by Series

I will give an introduction to the problem of sampling from a strongly log-concave density on Euclidean space through the lens of convex optimization.  In particular, I will focus on the interpretation, due to Jordan, Kinderlehrer, and Otto, of the...

High dimensional expanders are an exciting generalization of expander graphs to hypergraphs and other set systems.  Loosely speaking, high dimensional expanders are sparse approximation to the complete hypergraph.  In this talk, we’ll give a gentle...

Explicit constructions of "random-like" objects play an important role in complexity theory and pseudorandomness. For many important objects such as prime numbers and rigid matrices, it remains elusive to find fast deterministic algorithms for...

Consider a function on $R^n$ that can be written as a sum of functions $f = f_1$ + $f_2$ + ... + $f_m$, for $m >> n$.

The question of approximating f by a reweighted sum using only a small number of summands has many applications in CS theory...

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. In this talk, we present new explicit...

Coboundary expansion and cosystolic expansion are generalizations of edge expansion to hypergraphs. In this talk, we will first explain how the generalizations work. Next we will motivate the study of such hypergraphs by looking at their...

The online discrepancy minimization problem asks, given unit vectors v_1, ..., v_t arriving one at a time, for online signs x_1 ..., x_t4 in {-1, 1} so that the signed sum x_1 v_1 + ... + x_t v_t has small coordinates in absolute value. 

In the first...

Consider a scenario where we are learning a predictor, whose predictions will be evaluated by their expected loss. What if we do not know the precise loss at the time of learning, beyond some generic properties (like convexity)? What if the same...

I will prove that the block length of every linear 3-query Locally Correctable Code (LCC) with a constant distance over any small field grows exponentially with k, the dimension of the code. This result gives the first separation between LCCs and...

Consider the process where a signal propagates downward an infinite rooted tree. On every edge some independent noise is applied to the signal. The reconstruction problem asks whether it is possible to reconstruct the original signal given...

I will discuss recent progress on approximating the metric traveling salesperson problem, focusing on a line of work beginning in 2011 that studies the behavior of the max entropy algorithm. This algorithm is a randomized variant of the beautiful...

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

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

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

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

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

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

In a $3$-$\mathsf{XOR}$ game $\mathcal{G}$, the verifier samples a challenge $(x,y,z)\sim \mu$ where $\mu$ is a probability distribution over $\Sigma\times\Gamma\times\Phi$,  and a map $t\colon \Sigma\times\Gamma\times\Phi\to\mathcal{A}$ for a...

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

A cornerstone result in geometry is the Szemerédi–Trotter theorem, which gives a sharp bound on the maximum number of incidences between $m$ points and $n$ lines in the real plane. A natural generalization of this is to consider point-hyperplane...

A graph $G$ is said to be Ramsey for a tuple of graphs ($H_1,...,H_r$) if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$, for some $i$. A fundamental question at the intersection of Ramsey theory and the...

Chernoff's bound states that for any $A \subset [N]$ the probability a random $k$-tuple $s \in {[N] \choose k}$ correctly `samples' $A$ (i.e. that the density of $A$ in $s$ is close to its mean) decays exponentially in the dimension $k$. In 1987...

It was conjectured by Alon in the 1980s that random d-regular graphs have the largest possible spectral gap (up to negligible error) among all d-regular graphs. This conjecture was proved by Friedman in 2004 in major tour de force. In recent years...

In the previous talk, we defined Subgroup Tests and the interactive proof system induced by them. In addition, we showed that if the Aldous--Lyons conjecture was true, then this interactive proof system contains only decidable languages. In this...

The well-known Zig-Zag product and related graph operators, like derandomized squaring, are fundamentally combinatorial in nature. Classical bounds on their behavior often rely on a mix of combinatorics and linear algebra. However, these traditional...

I will discuss the Hanna Neumann conjecture of the 1950's and some tools in graph theory that I used to solve it.  The tools include sheaf theory on graphs, Galois theory for graphs, and the preservation of "local properties" under base change (for...

In this talk, I will elaborate on the main technical component of our PCP—the construction of routing protocols on high-dimensional expanders (HDX) that can withstand a constant fraction of edge corruptions. We consider the following routing problem...

The Brunn-Minkowski inequality is a fundamental result in convex geometry controlling the volume of  the sum of subsets of $\mathbb{R}^n$. It asserts that for  sets $A,B\subset \mathbb{R}^n$ of equal volume and a parameter $t\in(0,1)$, we have $|tA+...

The Brunn-Minkowski inequality is a fundamental result in convex geometry controlling the volume of  the sum of subsets of $\mathbb{R}^n$. It asserts that for  sets $A,B\subset \mathbb{R}^n$ of equal volume and a parameter $t\in(0,1)$, we have $|tA+...

Expander graphs are a staple of theoretical computer science. These are graphs which are both sparse and well connected. They are simple to construct and modify. Therefore they are a central gadget in numerous applications in TCS and combinatorics...

This is the introductory talk for a semester-long learning seminar on the notion of solid modules and the resulting 6-functor formalism for coherent cohomology.

Steven will cover the material from the first two lectures by Peter Scholze (available electronically at http://people.mpim-bonn.mpg.de/scholze/Condensed.pdf). In particular, he will introduce the notion of condensed set and condensed abelian group...

Quasi-coherent sheaves cannot support a six-functor formalism in the same way that e.g. \ell-adic sheaves do. Clausen and Scholze have shown that this can be fixed by extending the category of quasi-coherent sheaves to `solid sheaves’. In this talk...

This talk is an introduction to analytic rings. Some examples and non-examples will be covered. Some nice properties of the module categories will be proved.

We will discuss the notion of solid abelian groups.