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.