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.