Seminario Interdipartimentale di Algoritmica  

Monday, February 6, 2006, 12:00 noon
Gowers Uniformity, influence of variables, and PCPs
Alex Samorodnitsky, The Hebrew University of Jerusalem

DI - Department of Computer Science
Seminar Room, third floor

Abstract:

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.

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.

The second result is joint work with Luca Trevisan.