Document Open Access Logo

On Higher-Order Fourier Analysis over Non-Prime Fields

Authors Arnab Bhattacharyya, Abhishek Bhowmick, Chetan Gupta

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.23.pdf
  • Filesize: 0.63 MB
  • 29 pages

Document Identifiers

Author Details

Arnab Bhattacharyya
Abhishek Bhowmick
Chetan Gupta

Cite As Get BibTex

Arnab Bhattacharyya, Abhishek Bhowmick, and Chetan Gupta. On Higher-Order Fourier Analysis over Non-Prime Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 23:1-23:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.23

Abstract

The celebrated Weil bound for character sums says that for any low-degree polynomial P and any additive character chi, either chi(P) is a constant function or it is distributed close to uniform.  The goal of higher-order Fourier analysis is to understand the connection between the algebraic and analytic properties of polynomials (and functions, generally) at a more detailed level. For instance, what is the tradeoff between the equidistribution of chi(P) and its "structure"?

Previously, most of the work in this area was over fields of prime order. We extend the tools of higher-order Fourier analysis to analyze functions over general finite fields. Let K be a field extension of a prime finite field F_p. Our technical results are:

1. If P: K^n -> K is a polynomial of degree <= d, and E[chi(P(x))] > |K|^{-s} for some s > 0 and non-trivial additive character chi, then P is a function of O_{d, s}(1) many non-classical polynomials of weight degree < d. The definition of non-classical polynomials over non-prime fields is one of the contributions of this work.

2. Suppose K and F are of bounded order, and let H be an affine subspace of K^n. Then, if P: K^n -> K is a polynomial of degree d that is sufficiently regular, then (P(x): x in H) is distributed almost as uniformly as possible subject to constraints imposed by the degree of P. Such a theorem was previously known for H an affine subspace over a prime field.


The tools of higher-order Fourier analysis have found use in different areas of computer science, including list decoding, algorithmic decomposition and testing. Using our new results, we revisit some of these areas.

(i) For any fixed finite field K, we show that the list decoding radius of the generalized Reed Muller code over K equals the minimum distance of the code.

(ii) For any fixed finite field K, we give a polynomial time algorithm to decide whether a given polynomial P: K^n -> K can be decomposed as a particular composition of lesser degree polynomials.

(iii) For any fixed finite field K, we prove that all locally characterized affine-invariant properties of functions f: K^n -> K are testable with one-sided error.

Subject Classification

Keywords
  • finite fields
  • higher order fourier analysis
  • coding theory
  • property testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing Reed-Muller codes. IEEE Trans. Inform. Theory, 51(11):4032-4039, 2005. URL: http://dx.doi.org/10.1109/TIT.2005.856958.
  2. S. Arora and M. Sudan. Improved low-degree testing and its applications. Combinatorica, 23(3):365-426, 2003. Google Scholar
  3. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proc. 23rd Annual ACM Symposium on the Theory of Computing, pages 21-32, New York, 1991. ACM Press. Google Scholar
  4. László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1(1):3-40, 1991. Google Scholar
  5. Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, and Madhu Sudan. Symmetric LDPC codes are not necessarily locally testable. In Proc. 26th Annual Conference on Computational Complexity (CCC), pages 55-65. IEEE, 2011. Google Scholar
  6. Arnab Bhattacharyya. Polynomial decompositions in polynomial time. In Proc. 22nd Annual European Symposium on Algorithms, pages 125-136, 2014. Google Scholar
  7. Arnab Bhattacharyya and Abhishek Bhowmick. Using higher-order fourier analysis over general fields. CoRR, abs/1505.00619, 2015. URL: http://arxiv.org/abs/1505.00619.
  8. Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie. Testing linear-invariant non-linear properties. Theory Comput., 7(1):75-99, 2011. Google Scholar
  9. Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett. Every locally characterized affine-invariant property is testable. In Proc. 45th Annual ACM Symposium on the Theory of Computing, pages 429-436, 2013. Google Scholar
  10. Arnab Bhattacharyya, Eldar Fischer, and Shachar Lovett. Testing low complexity affine-invariant properties. In Proc. 24th ACM-SIAM Symposium on Discrete Algorithms, pages 1337-1355, 2013. Google Scholar
  11. Arnab Bhattacharyya, Elena Grigorescu, and Asaf Shapira. A unified framework for testing linear-invariant properties. In Proc. 51st Annual IEEE Symposium on Foundations of Computer Science, pages 478-487, 2010. Google Scholar
  12. Arnab Bhattacharyya, Pooya Hatami, and Madhur Tulsiani. Algorithmic regularity for polynomials and applications. In Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, pages 1870-1889, 2015. Google Scholar
  13. Abhishek Bhowmick and Shachar Lovett. Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory. CoRR, abs/1506.02047, 2015. URL: http://arxiv.org/abs/1506.02047.
  14. Abhishek Bhowmick and Shachar Lovett. List decoding Reed-Muller codes over small fields. In Proc. 47th Annual ACM Symposium on the Theory of Computing, pages 277-285, New York, NY, USA, 2015. ACM. Google Scholar
  15. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comp. Sys. Sci., 47:549-595, 1993. Earlier version in STOC'90. Google Scholar
  16. A. Bogdanov and E. Viola. Pseudorandom bits for polynomials. In Proc. 48^th IEEE Symp. on Foundations of Computer Science (FOCS'07), 2007. Google Scholar
  17. Pierre Deligne. Application de la formule des traces aux sommes trigonometriques. In SGA 4 \frac12 Springer Lecture Notes in Matematics, volume 569. Springer, 1978. Google Scholar
  18. P. Elias. List decoding for noisy channels. Technical Report 335, Research Laboratory of Electronics, MIT, 1957. Google Scholar
  19. Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268-292, 1996. Google Scholar
  20. O. Goldreich and L. Levin. A hard-core predicate for all one-way functions. In Proc. 21^st ACM Symposium on the Theory of Computing, pages 25-32, 1989. Google Scholar
  21. O. Goldreich, R. Rubinfeld, and M. Sudan. Learning polynomials with queries: The highly noisy case. SIAM J. Discrete Math., 13(4):535-570, 2000. Google Scholar
  22. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45:653-750, 1998. Google Scholar
  23. Oded Goldreich and Tali Kaufman. Proximity oblivious testing and the role of invariances. In Studies in Complexity and Cryptography, pages 173-190. Springer, 2011. Google Scholar
  24. Oded Goldreich and Dana Ron. On proximity oblivious testing. SIAM J. Comput., 40(2):534-566, 2011. Google Scholar
  25. P. Gopalan. A Fourier-analytic approach to Reed-Muller decoding. In Proc. 51^st IEEE Symp. on Foundations of Computer Science (FOCS'10), pages 685-694, 2010. Google Scholar
  26. P. Gopalan, A. Klivans, and D. Zuckerman. List decoding Reed-Muller codes over small fields. In Proc. 40^th ACM Symposium on the Theory of Computing (STOC'08), pages 265-274, 2008. Google Scholar
  27. Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer. Testing Fourier dimensionality and sparsity. In Proc. 36th Annual International Conference on Automata, Languages, and Programming, pages 500-512, 2009. Google Scholar
  28. William T. Gowers. A new proof of Szeméredi’s theorem for arithmetic progressions of length four. Geom. Funct. Anal., 8(3):529-551, 1998. Google Scholar
  29. William T. Gowers. A new proof of Szeméredi’s theorem. Geom. Funct. Anal., 11(3):465-588, 2001. Google Scholar
  30. Ben Green and Terence Tao. The distribution of polynomials over finite fields, with applications to the Gowers norms. Contrib. Discrete Math., 4(2), 2009. Google Scholar
  31. Elena Grigorescu, Tali Kaufman, and Madhu Sudan. Succinct representation of codes with applications to testing. SIAM Journal on Discrete Mathematics, 26(4):1618-1634, 2012. Google Scholar
  32. Alan Guo, Swastik Kopparty, and Madhu Sudan. New affine-invariant codes from lifting. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 529-540. ACM, 2013. Google Scholar
  33. V. Guruswami. List Decoding of Error-Correcting Codes, volume 3282 of Lecture Notes in Computer Science. Springer, 2004. Google Scholar
  34. V. Guruswami. Algorithmic Results in List Decoding, volume 2 of Foundations and Trends in Theoretical Computer Science. Now Publishers, 2006. Google Scholar
  35. Hamed Hatami and Shachar Lovett. Estimating the distance from testable affine-invariant properties. In Proc. 54th Annual IEEE Symposium on Foundations of Computer Science, pages 237-242. IEEE, 2013. Google Scholar
  36. Tali Kaufman and Simon Litsyn. Almost orthogonal linear codes are locally testable. In Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pages 317-326. IEEE, 2005. Google Scholar
  37. Tali Kaufman and Shachar Lovett. Worst case to average case reductions for polynomials. In Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pages 166-175, 2008. Google Scholar
  38. Tali Kaufman and Dana Ron. Testing polynomials over general fields. SIAM J. on Comput., 36(3):779-802, 2006. Google Scholar
  39. Tali Kaufman and Madhu Sudan. Algebraic property testing: the role of invariance. In Proc. 40th Annual ACM Symposium on the Theory of Computing, pages 403-412, 2008. Google Scholar
  40. Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky. Inverse conjecture for the Gowers norm is false. In Proc. 40th Annual ACM Symposium on the Theory of Computing, pages 547-556, New York, NY, USA, 2008. ACM. Google Scholar
  41. R. Pellikaan and X. Wu. List decoding of q-ary Reed-Muller codes. IEEE Transactions on Information Theory, 50(4):679-682, 2004. Google Scholar
  42. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. on Comput., 25:252-271, 1996. Google Scholar
  43. M. Sudan. Decoding of Reed-Solomon codes beyond the error-correction bound. Journal of Complexity, 13(1):180-193, 1997. URL: https://citeseer.ist.psu.edu/sudan97decoding.html.
  44. M. Sudan. List decoding: Algorithms and applications. SIGACT News, 31(1):16-27, 2000. Google Scholar
  45. M. Sudan, L. Trevisan, and S. P. Vadhan. Pseudorandom generators without the XOR lemma. J. Comput. Syst. Sci., 62(2):236-266, 2001. Google Scholar
  46. Terence Tao. Higher Order Fourier Analysis, volume 142 of Graduate Studies in Mathematics. American Mathematical Society, 2012. Google Scholar
  47. Terence Tao and Tamar Ziegler. The inverse conjecture for the Gowers norm over finite fields via the correspondence principle. Analysis &PDE, 3(1):1-20, 2010. Google Scholar
  48. Terence Tao and Tamar Ziegler. The inverse conjecture for the Gowers norm over finite fields in low characteristic. Ann. Comb., 16(1):121-188, 2012. Google Scholar
  49. Andre Weil. Sur les courbes algébriques et les varietes qui s'en deduisent. Actualites Sci. et Ind., 1041, 1948. Google Scholar
  50. J. Wozencraft. List decoding. Technical Report 48:90-95, Quarterly Progress Report, Research Laboratory of Electronics, MIT, 1958. Google Scholar
  51. Yuichi Yoshida. A characterization of locally testable affine-invariant properties via decomposition theorems. In Proc. 46th Annual ACM Symposium on the Theory of Computing, pages 154-163, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact