Document Open Access Logo

On Correlation Bounds Against Polynomials

Authors Peter Ivanov, Liam Pavlovic, Emanuele Viola

PDF
Thumbnail PDF

File

LIPIcs.CCC.2023.3.pdf
  • Filesize: 0.84 MB
  • 35 pages

Document Identifiers

Author Details

Peter Ivanov
  • Northeastern University, Boston, MA, USA
Liam Pavlovic
  • Northeastern University, Boston, MA, USA
Emanuele Viola
  • Northeastern University, Boston, MA, USA

Funding

NSF grant CCF-2114116
  • Pavlovic, Liam: Northeastern REU supplement

Acknowledgements

We are grateful to Brenden Collins for collaborating during the initial stages of this project.

Cite As Get BibTex

Peter Ivanov, Liam Pavlovic, and Emanuele Viola. On Correlation Bounds Against Polynomials. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 3:1-3:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CCC.2023.3

Abstract

We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over 𝔽₂. Our main contributions include:  
1) In STOC 2020, CHHLZ introduced a new technique to prove correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their technique generalizes to higher degree polynomials as well. We give a counterexample to their conjecture, in fact ruling out weaker parameters and showing what they prove is essentially the best possible. 
2) We propose a new approach for proving correlation bounds with the central "mod functions," consisting of two steps: (I) the polynomials that maximize correlation are symmetric and (II) symmetric polynomials have small correlation. Contrary to related results in the literature, we conjecture that (I) is true. We argue this approach is not affected by existing "barrier results."
3) We prove our conjecture for quadratic polynomials. Specifically, we determine the maximum possible correlation between quadratic polynomials modulo 2 and the functions (x_1,… ,x_n) → z^{∑ x_i} for any z on the complex unit circle, and show that it is achieved by symmetric polynomials. To obtain our results we develop a new proof technique: we express correlation in terms of directional derivatives and analyze it by slowly restricting the direction.
4) We make partial progress on the conjecture for cubic polynomials, in particular proving tight correlation bounds for cubic polynomials whose degree-3 part is symmetric.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Correlation bounds
  • Polynomials

Metrics

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

Related Versions

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: a new barrier in complexity theory. In 40th ACM Symp. on the Theory of Computing (STOC), pages 731-740, 2008. Google Scholar
  2. Noga Alon and Richard Beigel. Lower bounds for approximations by low degree polynomials over Z_m. In IEEE Conf. on Computational Complexity (CCC), pages 184-187, 2001. Google Scholar
  3. László Babai, Noam Nisan, and Márió Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. of Computer and System Sciences, 45(2):204-232, 1992. Google Scholar
  4. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P=?NP question. SIAM J. on Computing, 4(4):431-442, 1975. Google Scholar
  5. Michael Ben-Or and Nathan Linial. Collective coin flipping, robust voting schemes and minima of Banzhaf values. In 26th Symposium on Foundations of Computer Science, pages 408-416, Portland, Oregon, 21-23 October 1985. IEEE. Google Scholar
  6. Nayantara Bhatnagar, Parikshit Gopalan, and Richard J. Lipton. Symmetric polynomials over Z_m and simultaneous communication protocols. J. of Computer and System Sciences, 72(2):252-285, 2006. Google Scholar
  7. Abhishek Bhowmick and Shachar Lovett. Nonclassical polynomials as a barrier to polynomial lower bounds. In IEEE Conf. on Computational Complexity (CCC), pages 72-87, 2015. URL: https://doi.org/10.4230/LIPIcs.CCC.2015.72.
  8. Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola. Bounded independence versus symmetric tests. ACM Trans. Computation Theory, 11(4):21:1-21:27, 2019. Google Scholar
  9. Jean Bourgain. Estimation of certain exponential sums arising in complexity theory. Comptes Rendus Mathématique. Académie des Sciences. Paris, 340(9):627-631, 2005. Google Scholar
  10. Jin-Yi Cai, Frederic Green, and Thomas Thierauf. On the correlation of symmetric functions. Mathematical Systems Theory, 29(3):245-258, 1996. Google Scholar
  11. Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman. XOR lemmas for resilient functions against polynomials. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, ACM Symp. on the Theory of Computing (STOC), pages 234-246. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384242.
  12. Eduardo Dueñez, Steven J. Miller, Amitabha Roy, and Howard Straubing. Incomplete quadratic exponential sums in several variables. Journal of Number Theory, 116(1):168-199, 2006. Google Scholar
  13. Frederic Green. The correlation between parity and quadratic polynomials mod 3. J. of Computer and System Sciences, 69(1):28-44, 2004. Google Scholar
  14. Frederic Green, Daniel Kreymer, and Emanuele Viola. Block-symmetric polynomials correlate with parity better than symmetric. Computational Complexity, 26(2):323-364, 2017. Available at URL: https://www.ccs.neu.edu/home/viola/papers/blocksym.pdf.
  15. Frederic Green and Amitabha Roy. Uniqueness of optimal mod 3 circuits for parity. Journal of Number Theory, 130:961-975, 2010. Google Scholar
  16. Frederic Green, Amitabha Roy, and Howard Straubing. Bounds on an exponential sum arising in Boolean circuit complexity. Comptes Rendus Mathématique. Académie des Sciences. Paris, 341(5):279-282, 2005. Google Scholar
  17. András Hajnal, Wolfgang Maass, Pavel Pudlák, Márió Szegedy, and György Turán. Threshold circuits of bounded depth. J. of Computer and System Sciences, 46(2):129-154, 1993. Google Scholar
  18. Xuangui Huang, Peter Ivanov, and Emanuele Viola. Affine extractors and ac0-parity, 2021. Google Scholar
  19. Eric Miles and Emanuele Viola. Substitution-permutation networks, pseudorandom functions, and natural proofs. J. of the ACM, 62(6), 2015. Google Scholar
  20. Moni Naor, Omer Reingold, and Alon Rosen. Pseudorandom functions and factoring. SIAM J. Comput., 31(5):1383-1404, 2002. Google Scholar
  21. Ryan O'Donnell. Analysis of boolean functions, 2007. Lecture notes. Available at URL: http://www.cs.cmu.edu/~odonnell/boolean-analysis/.
  22. Alexander Razborov. Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Akademiya Nauk SSSR. Matematicheskie Zametki, 41(4):598-607, 1987. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987. Google Scholar
  23. Alexander Razborov and Steven Rudich. Natural proofs. J. of Computer and System Sciences, 55(1):24-35, August 1997. Google Scholar
  24. Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In 19th ACM Symp. on the Theory of Computing (STOC), pages 77-82. ACM, 1987. Google Scholar
  25. Roman Smolensky. On representations by low-degree polynomials. In 34th IEEE IEEE Symp. on Foundations of Computer Science (FOCS), pages 130-138, 1993. Google Scholar
  26. Terence Tao and Tamar Ziegler. The inverse conjecture for the gowers norm over finite fields in low characteristic. In Annals of Combinatorics, 2012. Google Scholar
  27. Emanuele Viola. New correlation bounds for GF(2) polynomials using Gowers uniformity. Electronic Colloquium on Computational Complexity, Technical Report TR06-097, 2006. URL: https://eccc.weizmann.ac.il/report/2006/097/.
  28. Emanuele Viola. Correlation bounds for polynomials over 0,1. SIGACT News, Complexity Theory Column, 40(1), 2009. Google Scholar
  29. Emanuele Viola. On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science, 5(1):1-72, 2009. Google Scholar
  30. Emanuele Viola. Challenges in computational lower bounds. SIGACT News, Open Problems Column, 48(1), 2017. Google Scholar
  31. Emanuele Viola. Fourier conjectures, correlation bounds, and majority. In Coll. on Automata, Languages and Programming (ICALP), 2021. Available at URL: https://www.ccs.neu.edu/home/viola/papers/L12requiresCor.pdf.
  32. Emanuele Viola. New lower bounds for probabilistic degree and AC0 with parity gates. Theory of Computing, 2021. Available at URL: https://www.ccs.neu.edu/home/viola/papers/diago.pdf.
  33. Emanuele Viola. Correlation bounds against polynomials, a survey, 2022. 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