Haifa University - Dept. of CS Theory Seminar

Speaker : Alex Samorodnitsky, Hebrew University.

Title: "Low degree tests at large distances".

Date: Thursday, May. 15.

Place: Haifa U. Education Building, room 566.

Time: 12:15 - 13:30

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.