Seminars Sorted by Series

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

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.