Seminars Sorted by Series

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

An epsilon-biased set X in {0,1}^n is a set so that for every non-empty set T in [n] the following holds. The random bit B(T) obtained by selecting at random a vector x in X, and computing the mod-2 sum of its T-coordinates, has bias at most epsilon...

The small-set expansion conjecture introduced by Raghavendra and Steuerer is a natural hardness assumption concerning the problem of approximating edge expansion of small sets (of size $\delta n$) in graphs. It was shown to be intimately connected...

The Stepanov method is an elementary method for proving bounds on the number of roots of polynomials. At its core is the following idea. To upper bound the number of roots of a polynomial f(x) in a field, one sets up an auxiliary polynomial F(x)...

In this talk I will insult your intelligence by showing a non-original proof of the Central Limit Theorem, with not-particularly-good error bounds. However, the proof is very simple and flexible, allowing generalizations to multidimensional and...

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms, that can recover any bit of the original message by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a...

We give a pseudorandom generator, with seed length O(log n), for CC0[p], the class of constant-depth circuits with unbounded fan-in MODp gates, for prime p. More accurately, the seed length of our generator is O(log n) for any constant error epsilon...

Finding the longest increasing subsequence (LIS) is a classic algorithmic problem. Simple O(n log n) algorithms, based on dynamic programming, are known for solving this problem exactly on arrays of length n. In this talk I'll discuss recent work of...

A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at...

Let f(x_1,...,x_n) be a low degree polynomial over F_p. I will prove that there always exists a small set S of variables, such that `most` Fourier coefficients of f contain some variable from the set S. As an application, we will get a derandomized...

The firefighter problem is a monotone dynamic process in graphs that can be viewed as modeling the use of a limited supply of vaccinations to stop the spread of an epidemic. In more detail, a fire spreads through a graph, from burning vertices to...

We give an elementary proof of a generalization of Bourgain and Tzafriri's Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well...

Infinite continuous graphs emerge naturally in the geometric analysis of closed planar sets which cannot be presented as countable union of convex sets. The classification of such graphs leads in turn to properties of large classes of real functions...

A permutation pi=(pi_{1},...,pi_{n}) is consecutive 123-avoiding if there is no sequence of the form pi_i pi_{i+1} pi_{i+2}. More generally, for S a collection of permutations on m+1 elements, this definition extends to define consecutive S...

A hardness escalation method applies a simple transformation that increases the complexity of a computational problem. Using multiparty communication complexity we present a generic hardness escalation method that converts any family of...

Erdos conjectured that N points in the plane determine at least c N (log N)^{-1/2} different distances. Building on work of Elekes-Sharir, Nets Katz and I showed that the number of distances is at least c N (log N)^{-1} . (Previous estimates had...

Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We provide a polynomial-time algorithm for this problem for any fixed number ($k$) of Gaussians in $n$ dimensions (even if...

Boolean Threshold Functions (BTF) arise in many contexts, ranging from computer science and learning theory to theoretical neurobiology. In this talk, I will present non-rigorous approaches developed in the statistical physics of disordered systems...

We study the complexity of computing some basic arithmetic operations over GF(2^n), namely computing q-th root and q-th residuosity, by constant depth arithmetic circuits over GF(2) (also known as AC^0(parity)). Our main result is that these...

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections...

The complexity of simple stochastic games (SSGs) has been open since they were defined by Condon in 1992. Such a game is played by two players, Min and Max, on a graph consisting of max nodes, min nodes, and average nodes. The goal of Max is to...

We study the local testabilty of sparse linear codes. This problem is intimately connected to the problem of tolerant linearity testing of Boolean functions under nonuniform distributions. We give linearity tests for several natural and interesting...

Non-relativization of complexity issues can be interpreted as giving evidence that these issues cannot be resolved by “black-box” techniques. We show that the assumption $DistNP \subseteq AvgP$ does not imply that $NP\subseteq BPP$ by relativizing...

We define a polynomial threshold function to be a function of the form f(x) = sgn(p(x)) for p a polynomial. We discuss some recent techniques for dealing with polynomial threshold functions, particular when evaluated on random Gaussians. We show how...

In this talk, I will give new proofs for the hardness amplification of fficiently samplable predicates and of weakly verifiable puzzles. More oncretely, in the first part of the talk, I will give a new proof of Yao's XOR-Lemma as well as related...

Given a matrix $A$, it can be shown that there is a vector $z \in 0,1^n$ for which $|Az|/|Z| \geq |A|_2/C \log(n)$ (a0/1 sum of columns of $A$ which witnesses its large spectral norm) for instance by discretizing the top singular vector of $A$ and...