An Elementary Proof of the Restricted Invertibility Theorem

Nikhil Srivastava
Institute for Advanced Study
November 9, 2010

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-invertible. Our proof gives the tightest known form of this result, is constructive, and provides a deterministic polynomial time algorithm for finding the desired subspace.

The Graph Removal Lemma

Jacob Fox
Massachusetts Institute of Technology
November 8, 2010

Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(nh) copies of H can be made H-free by removing o(n2) edges. We give a new proof which avoids Szemeredi's regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma. This answers questions of Alon and Gowers.

Ground States of the 2D Edwards-Anderson Spin Glass

Michael Damron
Princeton University
November 5, 2010

I will discuss the problem of determining the number of infinite-volume ground states in the Edwards-Anderson (nearest neighbor) spin glass model on $Z^D$ for $D \geq 2$. There are no complete results for this problem even in $D=2$. I will focus on this case and explain recent results which go some way toward proving that (with zero external field, so that ground states come in pairs, related by a global spin flip) there is only a single ground state pair (GSP).

Fourier Spectrum of Polynomials Over Finite Fields

Shachar Lovett
Institute for Advanced Study
November 2, 2010

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 sampling of elements in $F_p^n$ which `look uniform` to $f$.

The talk will be self contained, even though in spirit it is a continuation of my previous talk on pseudorandom generators for $CC0[p]$. Based on joint work with Amir Shpilka and Partha Mukhopadhyay.