CSAIL Event Calendar: Previous Series

Gowers Uniformity, Influence of Variables and Probabilistically

Speaker: Luca Trevisan , University of California at Berkeley
Date: October 31 2006
Time: 4:15PM to 5:30PM
Location: 32-G449 Patil/Kiva
Host: Ronitt Rubinfeld & Ran Canetti, MIT

The "Gowers uniformity norms" measure the "pseudorandomness" of
functions f:G->C where G is an abelian group and C are the complex
numbers. (The lower is the norm, the more pseudorandom is the
function.) Such norms have played a fundamental role in several
recent advances in additive combinatorics, including the
celebrated Green-Tao theorem on long arithmetic progressions
in the primes.

We discover an application of this notion to computational
complexity, namely, to the construction of probabilistically
checkable proofs (PCPs). Our main result is a construction of
PCPs where the verifier makes q boolean queries, has
error probability at most (q+1)/2^q, and recognizes
languages that are "Unique-Games-hard." This is the best
possible result up to a constant factor, in light of
recent results by Charikar et al.

Our construction has applications to proving hardness of
approximation for various problems, such as independent set
in bounded-degree graphs.

One of our technical contributions is a new result about
Gowers Uniformity norms. We show that if a function
is such that all its variables have low "influence," then the
function has also low Gowers uniformity.

See other events that are part of Theory Colloquium Fall 2006

See other events happening in October 2006