Speaker: Luca Trevisan UC Berkeley
Time: 2006-03-31 14:00-2006-03-31 15:00
Venue: FIT Building, Tsinghua University

Abstract:

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 combinatorITCS, 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. (Joint work with A. Samorodnitsky)