__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
**

**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**