On Correlation Bounds against Polynomials
Article No.: 3, Pages 1 - 35
Abstract
We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over F2. 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 (x1, ..., xn) → zΣ xi or 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.
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.
[2]
Noga Alon and Richard Beigel. Lower bounds for approximations by low degree polynomials over Zm. In IEEE Conf. on Computational Complexity (CCC), pages 184--187, 2001.
[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.
[4]
Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P=?NP question. SIAM J. on Computing, 4(4):431--442, 1975.
[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.
[6]
Nayantara Bhatnagar, Parikshit Gopalan, and Richard J. Lipton. Symmetric polynomials over Zm and simultaneous communication protocols. J. of Computer and System Sciences, 72(2):252--285, 2006.
[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.
[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.
[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.
[10]
Jin-Yi Cai, Frederic Green, and Thomas Thierauf. On the correlation of symmetric functions. Mathematical Systems Theory, 29(3):245--258, 1996.
[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.
[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.
[13]
Frederic Green. The correlation between parity and quadratic polynomials mod 3. J. of Computer and System Sciences, 69(1):28--44, 2004.
[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 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.
[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.
[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.
[18]
Xuangui Huang, Peter Ivanov, and Emanuele Viola. Affine extractors and ac0-parity, 2021.
[19]
Eric Miles and Emanuele Viola. Substitution-permutation networks, pseudorandom functions, and natural proofs. J. of the ACM, 62(6), 2015.
[20]
Moni Naor, Omer Reingold, and Alon Rosen. Pseudorandom functions and factoring. SIAM J. Comput., 31(5):1383--1404, 2002.
[21]
Ryan O'Donnell. Analysis of boolean functions, 2007. Lecture notes. Available at 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.
[23]
Alexander Razborov and Steven Rudich. Natural proofs. J. of Computer and System Sciences, 55(1):24--35, August 1997.
[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.
[25]
Roman Smolensky. On representations by low-degree polynomials. In 34th IEEE IEEE Symp. on Foundations of Computer Science (FOCS), pages 130--138, 1993.
[26]
Terence Tao and Tamar Ziegler. The inverse conjecture for the gowers norm over finite fields in low characteristic. In Annals of Combinatorics, 2012.
[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.
[29]
Emanuele Viola. On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science, 5(1):1--72, 2009.
[30]
Emanuele Viola. Challenges in computational lower bounds. SIGACT News, Open Problems Column, 48(1), 2017.
[31]
Emanuele Viola. Fourier conjectures, correlation bounds, and majority. In Coll. on Automata, Languages and Programming (ICALP), 2021. Available at 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 https://www.ccs.neu.edu/home/viola/papers/diago.pdf.
[33]
Emanuele Viola. Correlation bounds against polynomials, a survey, 2022.
Index Terms
- On Correlation Bounds against Polynomials
Recommendations
Tight Correlation Bounds for Circuits Between AC0 and TC0
CCC '23: Proceedings of the conference on Proceedings of the 38th Computational Complexity ConferenceWe initiate the study of generalized AC0 circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight ≥ k (up to negations of the input bits), which we denote GC0(k). The gate set of this class ...
Interlacing and spacing properties of zeros of polynomials, in particular of orthogonal and Lq-minimal polynomials, q∈[1,∞]
Let (P"2"n^*(z)) be a sequence of polynomials with real coefficients such that lim"nP"2"n^*(e^i^@f)=G(e^i^@f) uniformly for @f@__ __[@a-@d,@b+@d] with G(e^i^@f)<>0 on [@a,@b], where 0=<@a<@b=<@p and @d>0. First it is shown that the zeros of p"n(cos@f)=...
Nonclassical polynomials as a barrier to polynomial lower bounds
CCC '15: Proceedings of the 30th Conference on Computational ComplexityThe problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
In-Cooperation
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Dagstuhl, Germany
Publication History
Published: 29 August 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
CCC '23
CCC '23: conference on Proceedings of the 38th Computational Complexity Conference
July 17 - 20, 2023
Warwick, United Kingdom
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in