Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime

Details Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime

2011-04-17

arxiv.org/abs/1104.3335v1

Computer Science

Computational Complexity

43 pages. A preliminary version of this work appeared in STOC' 2011

Scientific paper

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:\mathbb{F}_p^n \rightarrow \mathbb{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 {\em 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 {\em 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 a nontrivial extension of a graph theoretical theorem of Erd\"os, Lov\'asz and Spencer to the context of additive number theory.

Affiliated with

Also associated with

No associations

Rating

Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-394424