Seminars Sorted by Series

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

A powerful technique developed and extended in the past decade in communication complexity is the so-called "lifting theorems."  The idea is to translate the hardness results from "easier" models, e.g., query complexity, polynomial degrees, to the...

The recently-discoverd Hypergraph Container Method (Saxton and Thomason, Balogh, Morris and Samotij), generalizing an earlier version for graphs (Kleitman and Winston), is used extensively in recent years in extremal and probabilistic combinatroics...

The online list labeling problem is a basic primitive in data structures. The goal is to store a dynamically-changing set of n items in an array of m slots, while keeping the elements in sorted order. To do so, some items may need to be moved over...

A seminal result in learning theory characterizes the PAC learnability of binary classes through the VC dimension. Extending this characterization to the general multiclass setting has been open since the late 1980s.

We resolve this problem by...

A Locally Decodable Codes (LDC) is an error correcting code which allows the decoding of a single message symbol from a few queries to a possibly corrupted encoding.  LDCs can be constructed, for example, from low degree polynomials over a finite...

Graph Crossing Number is a fundamental and extensively studied problem with wide ranging applications. In this problem, the goal is to draw an input graph $G$ in the plane so as to minimize the number of crossings between the images of its edges...

In this talk, I'll first give a broad overview of the history of combinatorial auctions within TCS, and then discuss some recent results.

Combinatorial auctions center around the following problem: There is a set M of m items, and N of n bidders...

Suppose we are given matchings $M_1,....,M_N$ of size t in some r-uniform hypergraph, and let us think of each matching having a different color. How large does N need to be (in terms of t and r) such that we can always find a rainbow matching of...

Robust sublinear expansion represents a fairly weak notion of graph expansion which still retains a number of useful properties of the classical notion. The general idea behind it has been introduced by Komlós and Szemerédi around 25 years ago and...

Randomness is a vital resource in computation, with many applications in areas such as cryptography, data-structures and algorithm design, sampling, distributed computing, etc. However generating truly random bits is expensive, and most sources in...

Suppose you have a set A of integers from {1, 2, …, N} that contains at least N / C elements.  Then for large enough N, must A contain three equally spaced numbers (i.e., a 3-term arithmetic progression)? 

In 1953, Roth showed that this is indeed...

A predicate $P:\Sigma^k \to {0,1}$ is said to be linearly embeddable if the set of assignments satisfying it can be embedded in an Abelian group. 

In this talk, we will present this notion and mention problems it relates to from various areas...

If $f$ is a real polynomial and $A$ and $B$ are finite sets of cardinality $n$, then Elekes and Ronyai proved that either $f(A\times B)$ is much larger than $n$, or $f$ has a very specific form (essentially, $f(x,y)=x+y$). In the talk I will tell...

The Lipschitz extension problem is the following basic “meta question” in metric geometry:  Suppose that X and Y are metric spaces and A is a subset of X. What is the smallest K such that every Lipschitz function f:A\to Y has an extension F:X\to Y...

We prove the existence of subspace designs with any given parameters, provided that the dimension of the underlying space is sufficiently large in terms of the other parameters of the design and satisfies the obvious necessary divisibility...

Discrepancy theory provides a powerful approach to improve upon the bounds obtained by a basic application of the probabilistic method. In recent years, several algorithmic approaches have been developed for various classical results in the area. In...

Let C be a class of metric spaces. We consider the following computational metric embedding problem: given a vector x in R^{n choose 2} representing pairwise distances between n points, change the minimum number of entries of x to ensure that the...

In the last few years, expanders have been used in fast graph algorithms in different models, including static, dynamic, and distributed algorithms. I will survey these applications of expanders, explain the expander-related tools behind this...

This talk will summarize a project I was involved in during the past 8 years. It started with attempts to understand the PIT (Polynomial Identity Testing) problem - a central problem involving randomness and hardness. It has led us to pursue many...

Linear dynamical systems are the canonical model for time series data. They have wide-ranging applications and there is a vast literature on learning their parameters from input-output sequences. Moreover they have received renewed interest because...

Random restrictions are a powerful tool used to study the complexity of boolean functions. Various classes of boolean circuits are known to simplify under random restrictions. A prime example of this, discovered by Subbotovskaya more than 60 years...

Recent years have seen remarkable progress in the field of Machine Learning (ML). 

However recent breakthroughs exhibit phenomena that remain unexplained and at times contradict conventional wisdom.  A primary reason for this discrepancy is that...

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