Seminars Sorted by Series

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

A d-dimensional framework is a pair $(G, \vec{p})$ consisting of a finite simple graph $G$ and an embedding $\vec{p}$ of its vertices in $\mathbb{R}^d$. A framework is called rigid if every continuous motion of the vertices in ${\mathbb R}^d$ that...

In 2023, Raghu Meka and I proved a substantially improved bound on the size of the smallest set of integers in [N] which contains no 3-term arithmetic progression. Since then, it has become clear that the main new ideas from that work are in fact...

In this talk we will discuss some recent progress on some questions in extremal combinatorics and in multiparty communication complexity.

We will also discuss some general connections between the two fields, emphasizing how certain problems (e.g...

Every word in a free group induces a probability distribution on every finite group by substituting the letters of w by uniformly random elements of the group. The connection between such distributions on the symmetric group and the poset of...

Error correcting codes are objects designed to withstand errors that may arise during communication. Originally intended for practical use, codes have come to be established as one of the central objects of study in theoretical computer science, due...

In this talk, we present a new method to solve algorithmic and combinatorial problems by (1) reducing them to bounding the maximum, over x in {-1, 1}^n, of homogeneous degree-q multilinear polynomials, and then (2) bounding the maximum value...

We present a new method to solve algorithmic and combinatorial problems by (1) reducing them to bounding the maximum, over x in {-1, 1}^n, of homogeneous degree-q multilinear polynomials, and then (2) bounding the maximum value attained by these...

Hindman’s Theorem states that whenever the natural numbers are finitely coloured there exists an infinite sequence all of whose finite sums are the same colour. By considering just powers of 2, this immediately implies the corresponding result for...

Positive selector processes are natural stochastic processes driven by sparse Bernoulli random variables. They play an important role in the study of suprema of general stochastic processes, and in particular, Talagrand posed the selector process...

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

Boosting is a fundamental and widely used method in machine learning, which determines that weak learnability of binary functions implies strong learnability. Traditionally, boosting theory has primarily focused on symmetric 0-1 loss functions...

Two matrices are called equivalent if one can be transformed into the other by multiplying with invertible matrices on the left and right. Extending this idea to 3-tensors, it is natural to define two 3-tensors as isomorphic if they can be...

In 2021 Avi gave a talk titled “Linear spaces of matrices” (see https://www.youtube.com/watch?v=H1H0OkZfZXw). As shown there, the study of linear spaces of matrices (which we call matrix spaces) arises naturally (and independently) in many different...

For every finite set of points in the plane, if every line going through any two of them contains a third, then they all lie on a single line. This ``local-to-global" theorem (which you can play with proving)  has many generalizations, to higher...

A locally testable code (LTC) is an error-correcting code equipped with a tester T that, given an input string x, queries only a small number of positions and rejects x with probability proportional to its distance from the code. Classic examples of...

High dimensional expansion comes in two flavors: spectral, which relates to random walks;  and cosystolic, which relates to chains of linear maps. The later is a more mysterious notion, which turns out related to a variety of applications such as...

A valency argument is an elegant and well-known technique for proving impossibility results in distributed computing. It is an example of an extension-based proof, which is modelled as an interaction between a prover and a protocol. Even though...

The $r$-colour Ramsey number $R_r(k)$ is the minimum $n \in \mathbb{N}$ such that every $r$-colouring of the edges of the complete graph $K_n$ on $n$ vertices contains a monochromatic copy of $K_k$. We prove, for each fixed $r \ge 2$, that 

$$R_r(k)...

We will go in-depth into the proof that for all functions $t(n) \geq n$, every multitape Turing machine running in time $t$ can be simulated in space only $O(\sqrt{t \log t})$. We will attempt to be completely self-contained. To that end, we will...

I will talk about the well known relation between cocycles and covers.  Then, I will discuss the relation of cocycle expansion to approximate covers, and finally how these show up in low-soundness PCP agreement tests.

In this talk, we will discuss new algorithms for solving instances of random and semirandom planted constraint satisfaction problems (CSPs). Random CSP are generated by first choosing a solution x and then sampling constraints so that x satisfies...

In this talk, I will begin with a quick primer to parameterized complexity, present some key insights from recent hardness of approximation results in the area, and end with a proof sketch of the following result: Assuming the Exponential Time...

Around 1992, Aldous made the following bold conjecture. Let A be any set of transpositions in the symmetric group Sym(N). Then the spectral gap of the Cayley graph Cay(Sym(N),A) is identical to that of a relatively tiny N-vertex graph defined by A...

Around 1992, Aldous made the following bold conjecture. Let A be any set of transpositions in the symmetric group Sym(N). Then the spectral gap of the Cayley graph Cay(Sym(N),A) is identical to that of a relatively tiny N-vertex graph defined by A...

Given linear equations over a finite field and under infinity norm, the Short-Integer-Solution (SIS^inf) problem asks to find a solution where each entry is a small number.

In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for...

Can we encode data in a way that it is recoverable even when 1) most data becomes corrupted, and 2) we can only read a sub-constant fraction of the database? This is the central question of local list decoding, a powerful tool from coding theory...

In this talk we will construct (approximate) locally list decodable codes from high dimensional expanders (HDXs).

Last week we saw that locally list decoding is a powerful tool from coding theory. We also got a subspace-based construction of...

Inspired by the Erdos--Renyi model for random graphs, Linial and Meshulam devised in 2006 a model for random 2-dimensional simplicial complexes. The goal of this talk (and the next) is to present some nice results about the behavior of these random...

Last week we defined the Linial--Meshulam model for random 2 dimensional simplicial complexes and discussed two notions of connectivity for it: Vanishing of its 1st cohomology with F2 coefficients, and vanishing of its fundamental group. This time...

The study of Turán numbers of graphs and hypergraphs is a rich problem in extremal combinatorics. The Turán problem asks, given a fixed forbidden (hyper)graph F, what is the maximum number of edges in an F-free (hyper)graph in terms of the number of...

The All-Pairs Min-Cut problem (APMC) asks to compute the minimum cut (or equivalently, the maximum flow) between all pairs of nodes in a graph.1 The naive solution of making n^2 calls to a single-pair min-cut algorithm was surpassed in 1961 by a...

Cryptographic primitives have been used for various non-cryptographic objectives, such as eliminating or reducing randomness and interaction. We show how to use cryptography to improve the time complexity of solving computational problems...

A line of work has shown how nontrivial uniform algorithms for analyzing circuits can be used to derive nonuniform circuit lower bounds. In this talk, I will show in depth how the nonexistence of nontrivial circuit-analysis algorithms can also imply...

We propose an extension of Yao's standard two-party communication model, where Alice and Bob respectively hold probability distributions p and q over inputs to a function f, rather than singleton inputs. Their goal is to estimate E[f(x,y)] to within...

Two vector spaces of the same finite dimension are related by a linear isomorphism; that’s how the dimension is defined. Similarly, two simple subalgebras over complex numbers that are closed under conjugate transpose are related by a unitary...

Over the past 50 years, cryptographers have constructed a number of surprising and important primitives like public-key encryption, which allows strangers to communicate privately even if eavesdroppers hear everything they say. However, there are...

In the theory of error-correcting codes, list decoding allows a decoder to output a list of candidates when attempting to remove noise from a corrupted input. The constructions and algorithms for such list decodable codes has had numerous...

The regularity lemma says that every discrete object can be partitioned into a small number of random-like subobjects. But how small is small? And can we make small smaller if we assume that our given object is simple? And what does it mean for a...