Topology of Norms Defined by Systems of Linear forms

Pooya Hatami
University of Chicago
May 7, 2012

Gowers' uniformity norms are defined by average of a function over specific sets of linear forms. We study norms that are similarly defined by a system of linear forms. We prove that for bounded complex functions over $F_p^n$, each such norm is equivalent to a Gowers' uniformity norm. To do this we prove direct and inverse theorems for norms defined by a system of linear forms.

Joint work with Shachar Lovett.

Pseudorandomness from Shrinkage

Raghu Meka
Institute for Advanced Study
May 8, 2012

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models where we only know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can indeed construct PRGs which are essentially best possible without in turn improving the lower bounds.