Israel CS THEORY DAY
Open University of
Division of Computer Science
Date: 17.3.08
Speaker: Alex Samorodnitsky
Title: Low degree tests at large distances
Abstract:
Consider the following problem: given a Boolean
function we need to decide whether it is "highly structured", which in
our case means representable by a low-degree
polynomial, or "pseudorandom", which we take to mean being far from
all low-degree polynomials. Our decision has to be based on a very restricted
randomized local view of the function.
This is a 'property testing' question with some existing and some potential
connections to probabilistically checkable proofs and derandomization.
We will discuss some recent developments regarding this question. In
particular, it turns out that an attempt to measure pseudorandomness
of a function analytically, via its 'Gowers norm',
does not work so well.
Based in part on joint work with Shachar Lovett, Roy Meshulam, and Luca Trevisan