Computer Science/Discrete Mathematics Seminar II

The uniformity norms are defined in different contexts in order to distinguish the ``typical'' random functions, from the functions that contain certain structures. A typical random function has small uniformity norms, while a function with a non-negligible uniformity norm correlates with a very structured function, e.g. a rank one function, a low degree polynomial, a nil-sequence. Such facts are useful for proving the existence of sub-structures (e.g. arithmetic progressions) inside larger structures. They are also interesting from the perspective of computer science. They provide ``tests'' for certain correlation problems. Roughly speaking, such tests show that for certain sets D , and every bounded function f , by ``reading'' the value of f on a small number of points it is possible to probabilistically distinguish between the following two cases: (i) There is an element in D which has a non-negligible correlation with f . (ii) Element of D have small correlations with f . The purpose of this talk is to investigate whether such results are specific to Gowers uniformity norms, or are there other cases where similar tests exist. I will show that essentially one cannot do more, and the cases implied by uniformity norms are the only possible instances where such tests exist. However we leave the case of low characteristic fields which is of great importance from the perspective of computer science open. This talk is based on a joint work with Shachar Lovett.