Gowers Uniformity, influence of variables, and PCPs

We prove two structural results for functions on the boolean cube with
high Gowers uniformity norms.

First – a boolean function with a large 3-rd uniformity norm is globally
correlated with a quadratic polynomial. We discuss the connection of this
result to recent developments in 'quadratic Fourier analysis'.

Second, a function with a large uniformity norm of any order has a highly
influential variable. This result is used to obtain conditional hardness
of approximation results. For instance, assuming the Unique Games
Conjecture is true, it is hard to approximate the cardinality of a maximal
independent subset of a graph of degree d within a factor of polylog(d)/d.

Much of this work is joint with Luca Trevisan.

Alex Samorodnitsky received all his degrees in math and computer science
from the Hebrew University of Jerusalem. He joined the CS department of
HUJI in 2001. His research interests are in theoretical computer science,
coding theory, and combinatorics.