Seminars Sorted by Series

A polynomial with nonnegative coefficients is strongly log-concave if it and all of its derivatives are log-concave as functions on the positive orthant. This rich class of polynomials includes many interesting examples, such as homogeneous real...

A polynomial with nonnegative coefficients is strongly log-concave if it and all of its derivatives are log-concave as functions on the positive orthant. This rich class of polynomials includes many interesting examples, such as homogeneous real...

Expander graphs are graphs which simultaneously are both sparse and highly connected. The theory of expander graphs received a lot of attention in the past half a century, from both computer science and mathematics. In recent years, a new theory of...

Expander graphs are graphs which simultaneously are both sparse and highly connected. The theory of expander graphs received a lot of attention in the past half a century, from both computer science and mathematics. In recent years, a new theory of...

This talk gives an introduction on how to quickly solve linear systems where the matrix of the system is the Laplacian matrix of any undirected graph. No prior familiarity with optimization is assumed. In the process, we will cover:

• what positive...

This talk introduces a directed analog of the classical Laplacian matrix and discusses algorithms for solving certain problems related to them. Of particular interest is that using such algorithms, one can compute the stationary distribution of a...

Random sampling a subgraph of a graph is an important algorithmic technique.  Solving some problems on the (smaller) subgraph is naturally faster, and can give either a useful approximate answer, or sometimes even give a result that can be quickly...

Bernstein's theorem (also known as the Bernstein-Khovanskii-Kushnirenko theorem) gives a bound on the number of nonzero solutions of a polynomial system of equations in terms of the mixed volume of its Newton polytopes. In this talk, we will give...

Some of the central questions in complexity theory address the amortized complexity of computation (also sometimes known as direct sum problems). While these questions appear in many contexts, they are all variants of the following: 

Is the best...

In a plethora of random models for constraint satisfaction and statistical inference problems, researchers from different communities have observed computational gaps between what existential or brute-force methods promise, and what known efficient...

The Satisfiability problem is perhaps the most famous problem in theoretical computer science, and significant effort has been devoted to understanding randomly generated SAT instances. The random k-SAT model (where a random k-CNF formula is chosen...

In the mid 80's, Bourgain asked the following question: Is there a universal constant $c>0$ such that every compact convex set $K$ in $R^n$, of unit volume, must contain a slice (namely, a set of the form $K \cap H$ for some affine hyperplane $H$)...

This is the second talk in a 3-lecture series whose goal is to give background as well as a self contained proof of Chen's recent breakthrough on the KLS conjecture and slicing problem (a video of the first lecture can be found here:

https://www...

This is the final talk in a 3-part series whose goal is to give background as well as a self contained proof of Chen's recent breakthrough on the KLS conjecture and slicing problem. After becoming familiar with the construction of stochastic...

The study of linear spaces of matrices arises naturally (and independently) in many different areas of mathematics and computer science.  In this survey talk, I will describe some of these motivations, and state and prove some (old and new)...

Every multivariate polynomial P(x_1,...,x_n) can be written as a sum of monomials, i.e. a sum of products of variables and field constants.  In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P...

The query model is one of the most basic computational models.  In contrast to the Turing machine model, fundamental questions regarding the power of randomness and quantum computing are relatively well-understood.  For example, it is well-known...

The query model is one of the most basic computational models.  In contrast to the Turing machine model, fundamental questions regarding the power of randomness and quantum computing are relatively well-understood.  For example, it is well-known...

A random point process is said to be determinantal if finite subset probabilities correspond to principal minors of some matrix. Determinantal point processes (DPPs) appear in a wide variety of settings, from random matrix theory to combinatorics...

A locally testable code (LTC) is an error correcting code that admits a very efficient membership test. The tester reads a constant number of (randomly - but not necessarily uniformly - chosen) bits from a given word and rejects words with...

The field of continuous combinatorics studies large (dense) combinatorial structures by encoding them in a "continuous" limit object, which is amenable to tools from analysis, topology, measure theory, etc. The syntactic/algebraic approach of "flag...

The field of continuous combinatorics studies large (dense) combinatorial structures by encoding them in a "continuous" limit object, which is amenable to tools from analysis, topology, measure theory, etc. While the syntactic/algebraic approach of...

As solutions can be efficiently verified, any NP-complete problem can be solved by exhaustive search. Unfortunately, even for small instances the running time for exhaustive search becomes very high. 

On the bright side, for many NP-complete...

A binary code is simply any subset of 0/1 strings of a fixed length. Given two strings, a standard way of defining their distance is by counting the number of positions in which they disagree. Roughly speaking, if elements of a code are sufficiently...

Expander graphs are sparse and yet well-connected graphs. Several applications in theoretical computer science require explicit constructions of expander graphs, sometimes even with additional structure. One approach to their construction is to...

Consider the action of a group on a finite-dimensional vector space. Given some natural conditions on the group, Hilbert showed a famous "duality" between invariant polynomials and closures of group orbits. Namely, the orbit closure of a vector is...

I will discuss the difficult problem of proving reasonable bounds in the multidimensional generalization of Szemerédi's theorem.  Most of the first talk will be spent going over Shkredov's proof of good bounds for sets lacking corners, in...

I will discuss the difficult problem of proving reasonable bounds in the multidimensional generalization of Szemerédi's theorem. Most of the first talk will be spent going over Shkredov's proof of good bounds for sets lacking corners, in preparation...

This is the first talk in a three-part series presented together with Lijie Chen.

The series is intended to survey the fast-paced recent developments in the study of derandomization. We will present:

1. A revised version of the classical hardness...

This is the second talk in a three-part series presented together with Roei Tell.

The series is intended to survey the fast-paced recent developments in the study of derandomization. We will present:

1. A revised version of the classical hardness...

This is the third and final talk in the joint series with Lijie Chen. The talk will NOT rely on the technical contents from the two previous talks.

I will present a joint work with Lijie, in which we revise the hardness vs randomness framework so...

In recent years, a new “fine-grained” theory of computational hardness has been developed, based on “fine-grained reductions” that focus on exact running times for problems. 

We follow the fashion of NP-hardness in a more delicate manner. We...

Two recent and seemingly-unrelated techniques for proving mixing bounds for Markov chains are:

(i) the framework of Spectral Independence, introduced by Anari, Liu and Oveis Gharan, and its numerous extensions, which have given rise to several...

Two recent and seemingly-unrelated techniques for proving mixing bounds for Markov chains are:

(i) the framework of Spectral Independence, introduced by Anari, Liu and Oveis Gharan, and its numerous extensions, which have given rise to several...

The absorption method is a very simple yet surprisingly powerful idea coming from extremal combinatorics which allows one to convert asymptotic results into exact ones. It has produced a remarkable number of success stories in recent years with...

The study of nodal sets, i.e. zero sets of eigenfunctions, on geometric objects can be traced back to De Vinci, Galileo, Hook, and Chladni. Today it is a central subject of spectral geometry. Sturm (1836) showed that the n-th eigenfunction of the...

Training a predictor to minimize a loss function fixed in advance is the dominant paradigm in machine learning. However, loss minimization by itself might not guarantee desiderata like fairness and accuracy that one could reasonably expect from a...

Gaussian elimination is one of the oldest and most well-known algorithms for solving a linear system. In this talk, we give a basic, yet thorough overview of the algorithm, its variants, and standard error and conditioning estimates. In addition, a...

One of the central problems of coding theory is to determine the trade-off between the amount of information a code can carry (captured by its rate) and its robustness to resist message corruption (captured by its distance). On the existential side...

One of the central problems of coding theory is to determine the trade-off between the amount of information a code can carry (captured by its rate) and its robustness to resist message corruption (captured by its distance). One of the main methods...

Expander graphs have been perhaps one of the most widely useful classes of graphs ever considered. In this talk we will focus on a fairly weak notion of expanders called sublinear expanders, first introduced by Komlos and Szemeredi around 25 years...

Expander graphs are fundamental objects in theoretical computer science and mathematics. They have numerous applications in diverse fields such as algorithm design, complexity theory, coding theory, pseudorandomness, group theory, etc.

In this talk...

The lifeblood of interactive proof systems is randomness, without which interaction becomes redundant. Thus, a natural long-standing question is which types of proof systems can indeed be derandomized and collapsed to a single-message NP-type...

We give the first almost-linear time algorithm for computing exact maximum flows and minimum-cost flows on directed graphs. By well known reductions, this implies almost-linear time algorithms for several problems including bipartite matching...

The theory of graph quasirandomness studies sequences of graphs that "look like" samples of the Erdős--Rényi random graph. The upshot of the theory is that several ways of comparing a sequence with the random graph turn out to be equivalent. For...

In this talk I will first review some basics about communication complexity.  Secondly I will survey some (old and new) equivalences between central problems in communication complexity and related questions in additive combinatorics.  In particular...