Seminars Sorted by Series

The P vs. NP problem has sometimes been unofficially paraphrased as asking whether it is possible to improve on exhaustive search for such problems as Satisfiability, Clique, Graph Coloring, etc. However, known algorithms for each of these problems...

The Resolution proof system is among the most basic and popular for proving propositional tautologies, and underlies many of the automated theorem proving systems in use today. I'll start by defining the Resolution system, and its place in the proof...

A randomness extractor is an efficient algorithm which extracts high-quality randomness from a low-quality random source. Randomness extractors have important applications in a wide variety of areas, including pseudorandomness, cryptography...

In this talk I will present a colored version of Tverberg's theorem about partitioning finite point sets in R^d into rainbow groups whose convex hulls intersect. This settles the famous Bárány-Larman conjecture (1992) for primes minus one, and...

In FT-mollification, one smooths a function while maintaining good quantitative control on high-order derivatives. I will describe this approach and show how it can be used to show that bounded independence fools polynomial threshold functions over...

In FT-mollification, one smooths a function while maintaining good quantitative control on high-order derivatives. This is a continuation of my talk from last week, and I will continue to describe this approach and show how it can be used to show...

The polynomial Freiman-Ruzsa conjecture is one of the important open problems in additive combinatorics. In computer science, it already has several diverse applications: explicit constructions of two-source extractors; improved bounds for the log...

A basic fact of algebraic graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only...

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs...

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching 1 while simultaneously allowing for sublinear-time error-correction. In this...

A property of finite graphs is called nondeterministically testable if it has a "certificate'' such that once the certificate is specified, its correctness can be verified by random local testing. In this talk we consider certificates that consist...

We consider the problem of constructing pseudorandom generators for read-once circuits. We give an explicit construction of a pseudorandom generator for the class of read-once constant depth circuits with unbounded fan-in AND, OR, NOT and...

We prove new lower bounds on the encoding length of Matching Vector (MV) codes. These recently discovered families of Locally Decodable Codes (LDCs) originate in the works of Yekhanin and Efremenko and are the only known families of LDCs with a...

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a...

A $q$-query Locally Decodable Code (LDC) is an error-correcting code that allows to read any particular symbol of the message by reading only $q$ symbols of the code word. In this talk we present a new approach for the construction of LDCs from the...

In this seminar I will discuss the details of the result that knottedness is in NP assuming the generalized Riemann hypothesis. The main part of the work is to properly understand Koiran's construction that solvability of a system of algebraic...

Shor's algorithm, the hallmark quantum algorithmic breakthrough, has been successfully generalized to address a variety of related algebraic problems. Generalizations to nonabelian settings could have striking consequences, but such efforts have...

A twenty-year old conjecture by Manickam, Mikl\'os, and Singhi asked whether for any integers $n, k$ satisfying $n \ge 4k$, every set of $n$ real numbers with nonnegative sum always has at least $\binom{n-1}{k-1}$ $k$-element subsets whose sum is...

One of the major insights of the ``fixed-parameter tractability’’ (FPT) approach to algorithm design is that, for many NP-hard problems, it is possible to efficiently *shrink* instances which have some underlying simplicity. This preprocessing can...

I present some of the very fundamental notions in game theory, with emphasis on their role in the theory of mechanism design and implementation. Examples include (1) normal-form games: Nash equilibrium and full implementation, dominant strategy...

Many problems from complexity theory can be phrased in terms of tensors. I will begin by reviewing basic properties of tensors and discussing several measures of the complexity of a tensor. I'll then focus on the complexity of matrix multiplication...

Some important mechanisms considered in game theory require solving optimization problems that are computationally hard. Solving these problems approximately may not help, as it may change the players’ rational behavior in the original mechanisms...

The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms...

We will give an overview of this system, which has been at the center of recent algorithmic and proof complexity developments. We will give the definitions of the system (as a proof system for polynomial inequalities, and as an SDP-based algorithm)...

An “oblivious subspace embedding” (OSE) is a distribution over matrices S such that for any low-dimensional subspace $V$, with high probability over the choice of $S$, $\|Sx\|_2$ approximately equals $\|x\|_2$ (up to $1 + \epsilon$ multiplicative...

Abstract: We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. In particular, we show: (1) The sparsity achieved by [Kane-Nelson, SODA 2012] in the sparse Johnson-Lindenstrauss lemma is optimal up...

A linear property of Banach spaces is called "local" if it depends on finite number of vectors and is invariant under renorming (i.e., distorting the norm by a finite factor). A famous theorem of Ribe states that local properties are invariant under...

Ultrametrics are special metrics satisfying a strong form of the triangle inequality: For every $x, y, z$, $d(x, z) \impliedby \max\{d(x, y), d(y, z)\}$. We consider Ramsey-type problems for metric spaces of the following flavor:

Every metric space...

Expander graphs, in general, and Ramanujan graphs, in particular, have been objects of intensive research in the last four decades. Many application came out, initially to computer science and combinatorics and more recently also to pure mathematics...

I will describe the very recent breakthrough result by Gupta, Kamath, Kayal and Saptharishi which shows that every polynomial P in n variables, of degree d which is polynomial in n, and which can be computed by a polynomial sized arithmetic circuit...

I will survey some of the basic approaches to derandomizing Probabilistic Logspace computations, including the "classical" Nisan, Impagliazzo-Nisan-Widgerson and Reingold-Raz generators, the Saks-Zhou algorithm and some more recent approaches. We'll...

I will continue the exposition of different derandmization techniques for probabilistic logspace algorithms. The material of this talk will assume only little knowledge from the first talk.

There are two important measures of the complexity of a boolean function: the sensitivity and block sensitivity. Whether or not they are polynomial related remains a major open question. In this talk I will survey some known results on this...

There are two important measures of the complexity of a boolean function: the sensitivity and block sensitivity. Whether or not they are polynomial related remains a major open question. In this talk I will survey some known results on this...

We give an arithmetic version of the recent proof of the improved triangle removal lemma by Fox [Fox11], for the group F_2^n. A triangle in F_2^n is a tuple (x,y,z) such that x+y+z = 0. The triangle removal lemma for F_2^n states that for every \eps...

We all know Shannon's entropy of a discrete probability distribution. Physicists define entropy in thermodynamics and in statistical mechanics (there are several competing schools), and want to prove the Second Law, but they didn't succeed yet (very...

Informally, uncertainty principle says that function and its Fourier transform can not be both concentrated. Uncertainty principle has a lot of applications in areas like compressed sensing, error correcting codes, number theory and many others. In...

We study algorithms for combinatorial market design problems, where a collection of objects are priced and sold to potential buyers subject to equilibrium constraints. We introduce the notion of a combinatorial Walrasian equilibium (CWE) as a...

The Kakeya and restriction conjectures are two of the central open problems in Euclidean Fourier analysis (with the second logically implying the first, and progress on the first typically implying progress on the second). Both of these have...

A common way for lower bounding the expansion of a graph is by looking the second smallest eigenvalue of its Laplacian matrix. Also known as the easy direction of Cheeger's inequality, this bound becomes too weak when the expansion is \(o(1)\). In...