COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Correlation testing for affine invariant properties on F_p^n

## Correlation testing for affine invariant properties on F_p^nAdd to your list(s) Download to your calendar using vCal - Lovett, S (IAS Princeton)
- Wednesday 04 May 2011, 14:00-15:00
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Discrete Analysis Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function $f:F_p^n ightarrow F_p$ with polynomials of degree at most $d le p$ is non-negligible, while making only a constant number of queries to the function. This is an instance of {m correlation testing}. In this framework, a fixed test is applied to a function, and the acceptance probability of the test is dependent on the correlation of the function from the property. This is an analog of {m proximity oblivious testing}, a notion coined by Goldreich and Ron, in the high error regime. In this work, we study general properties which are affine invariant and which are correlation testable using a constant number of queries. We show that any such property (as long as the field size is not too small) can in fact be tested by Gowers uniformity tests, and hence having correlation with the property is equivalent to having correlation with degree $d$ polynomials for some fixed $d$. We stress that our result holds also for non-linear properties which are affine invariant. This completely classifies affine invariant properties which are correlation testable. The proof is based on higher-order Fourier analysis. Another ingredient is an extension of a graph theoretical theorem of Erd”os, Lov’asz and Spencer to the context of additive number theory. Joint work with Hamed Hatami. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsArrol Adam Lectures 2016 | The Problem with Economics Institute of Astronomy Galaxies Discussion Group Meeting the Challenge of Healthy Ageing in the 21st Century## Other talksChallenges to monetary policy in a global context Multi-Index Stochastic Collocation (MISC) for Elliptic PDEs with random data Changing languages in European Higher Education: from official policies to unofficial classroom practices Magnetic microscopy of meteorites: probing the magnetic state of the early solar system Volcanoes and Explosions |