Seminars Sorted by Series

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

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