Seminars Sorted by Series

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Tao and Ziegler showed some general conditions...

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Tao and Ziegler showed some general conditions...

Affine extractors are maps over F^n that are balanced on every affine subspace of large enough dimension. A random map is, with high probability, a good affine extractor. However so far we do not know how to build explicit affine extractors that are...

Does computing n copies of a function require n times the computational effort? In this work, we give the first non-trivial answer to this question for the model of randomized communication complexity. We show that: 1. Computing n copies of a...

The Parallel Repetition Theorem by Raz is used to amplify the soundness of PCP's, and is one of the ingredients to prove strong inapproximability results. Unfortunately, Raz's proof was very complicated. In these two talks, I will present the...

Planarity is a central theme in graph theory and combinatorial geometry, dating back to Euler. There are many beautiful characterizations of planar graphs such as Kuratowski's forbidden minor theorem and Koebe's circle packing theorem from the 1930s...

The list decoding problem consists of finding the list of all codewords that differ from an input string (the received word) in at most a certain fraction of positions (equal to the target error-correction radius). Informally, the list decoding...

In this talk, we will discuss how the circle method can be used to count solutions to Diophantine problems. After a brief overview of the circle method's history and applications, we will sketch how to prove an asymptotic for the number of integer...

It has been checked, for zillions of even numbers, that they can all be expressed as a sum of two primes. It has also been checked for zillions of (non-trivial) zeros of Zeta(s), that their real parts are all equal to one half. Alas, these checks do...

In their seminal paper Feder and Vardi proved that every problem in the class Monotone Monadic Strict NP (MMSNP) is random polynomial-time equivalent to a finite union of Constraint Satisfaction Problems (CSP). The class MMSNP is the "largest...

We study solution sets to systems of 'generalized' linear equations of the form ell_i (x_1, x_2,...,x_n) \in A_i (mod m) where ell_1,...,ell_t are linear forms in n Boolean variables, each A_i is an arbitrary subset of Z_m, and m is a composite...

The 'method of multiplicities' (which is a variant of the polynomial method in combinatorics) is a very effective method to derive combinatorial bounds on the size of certain sets in vector spaces over finite fields. In this work we extend this...

An affine disperser over F_2^n for sources of dimension d is a function f: F_2^n --> F_2 such that for any affine subspace S in F_2^n of dimension at least d, we have {f(s) : s in S} = F_2 . Affine dispersers have been considered in the context of...

In his seminal work, Valiant defined algebraic analogs for the classes P and NP, which are known today as VP and VNP. He also showed that the permanent is VNP-complete (that is, the permanent is in VNP and any problem in VNP is reducible to it). We...

The general adversary bound is a lower bound on the number of input queries required for a quantum algorithm to evaluate a boolean function. We show that this lower bound is in fact tight, up to a logarithmic factor. The proof is based on span...

In his seminal work, Valiant defined algebraic analogs for the classes P and NP, which are known today as VP and VNP. He also showed that the permanent is VNP-complete (that is, the permanent is in VNP and any problem in VNP is reducible to it). We...

We present two new approximation algorithms for Unique Games. The first generalizes the results of Arora et al. who give polynomial time approximation algorithms for graphs with high conductance. We give a polynomial time algorithm assuming only...

The PCP Theorem shows that any mathematical proof can be efficiently converted into a form that can be checked probabilistically by making only *two* queries to the proof, and performing a "projection test" on the answers. This means that the answer...

I will survey some constructions of expander graphs using variants of Kazhdan property T . First, I describe an approach to property T using bounded generation and then I will describe a recent method based on the geometric properties of...

I will first give an overview of several constructions of graph sparsifiers and their properties. I will then present a method of sparsifying a subgraph W of a graph G with optimal number of edges and talk about the implications of subgraph...

I will discuss the Green-Tao proof for existence of arbitrarily long arithmetic progressions in the primes. The focus will primarily be on the parts of the proof which are related to notions in complexity theory. In particular, I will try to...

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Reingold, Trevisan, Tulsiani and Vadhan, and...

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Reingold, Trevisan, Tulsiani and Vadhan, and...

We give an algorithmic proof of Forster's Theorem, a fundamental result in communication complexity. Our proof is based on a geometric notion we call radial isotropic position which is related to the well-known isotropic position of a set of vectors...

Motivated in part by various sequences of graphs growing under random rules (like internet models), convergent sequences of dense graphs and their limits were introduced by Borgs, Chayes, Lovasz, Sos and Vesztergombi and by Lovasz and Szegedy. In...

In this survey lecture (which will continue on Tue Feb 2) I plan to explain basic aspects of the representation theory of finite groups, and how these are applied to various questions regarding expansion and random walks on groups. These...

In this survey lecture (which will continue on Tue., Feb 2) I plan to explain basic aspects of the representation theory of finite groups, and how these are applied to various questions regarding expansion and random walks on groups. These...

In this survey lecture (which will be continued), I plan to explain basic aspects of the representation theory of finite groups, and how these are applied to various questions regarding expansion and random walks on groups. These applications...

Is there a common explanation for 2SAT being solvable polynomial time, and Max2SAT being approximable to a 0.91 factor? More generally, it is natural to wonder what characterizes the complexity of exact constraint satisfaction problems (CSP) like...

The uniformity norms are defined in different contexts in order to distinguish the ``typical'' random functions, from the functions that contain certain structures. A typical random function has small uniformity norms, while a function with a non...

Collateralized Default Obligations (CDOs) and related financial derivatives have been at the center of the last financial crisis and subject of ongoing regulatory overhaul. Despite their demonstrable benefits in economic theory, derivatives suffer...

This talk will be concerned with how well can we approximate NP-hard problems. One of the most successful algorithmic strategies, from an upper bound perspective, is to write a polynomial time computable relaxation for an NP-hard problem and present...

We shall discuss new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is (either 0 or) 2. For every width d and length n, the pseudorandom...

Intensive study throughout the last three decades has yielded a rigorous understanding of the spectral-gap of the Glauber dynamics for the Ising model on $Z^2$ everywhere except at criticality. While the critical behavior of the Ising model has long...

A locally decodable code (LDC) is an error correcting code that allows for probabilistic decoding of a single message bit by reading a corrupted encoding in a small number of locations. Until recently, the only LDC constructions known where based on...

We consider the problem of approximately solving a system of homogeneous linear equations over reals, where each equation contains at most three variables. Since the all-zero assignment always satisfies all the equations exactly, we restrict the...

Sparse recovery problems arise in many applications. Suppose v is an unknown N-dimensional signal with at most k nonzero components. We call such signals k-sparse. Suppose we are able to collect n \ll N linear measurements of v , and wish to...