Gowers Uniformity, Influence of Variables and Probabilistically
Speaker: Luca Trevisan , University of California at BerkeleyContact:
Date: October 31 2006
Time: 4:15PM to 5:30PM
Location: 32-G449 Patil/Kiva
Host: Ronitt Rubinfeld & Ran Canetti, MIT
Kevin Matulef, firstname.lastname@example.orgRelevant URL: http://theory.lcs.mit.edu/theory-seminars/calendar.html
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