Guest Column: correlation bounds for polynomials over {0 1}

ABSTRACT

This article is a unified treatment of the state-of-the-art on the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over {0 1 }. It discusses long-standing results and recent developments, related proof techniques, and connections with pseudorandom generators. It also suggests several research directions.

REFERENCES

• 1: Noga Alon , Richard Beigel, Lower Bounds for Approximations by Low Degree Polynomials Over Z_m, Proceedings of the 16th Annual Conference on Computational Complexity, p.184, June 18-21, 2001
• 2: Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach (Draft). January 2007.
• 3: J. Aspnes, R. Beigel, M. Furst, and S. Rudich. The expressive power of voting polynomials. Combinatorica, 14(2):135--148, 1994.
• 4: Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289--304, 1992.
• 5: Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing low-degree polynomials over GF(2). In 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), volume 2764 of Lecture Notes in Computer Science, pages 188--199. Springer, 2003.
• 6: Scott Aaronson , Avi Wigderson, Algebrization: a new barrier in complexity theory, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374481]
• 7: Richard Beigel. The polynomial method in circuit complexity. In 8th Annual Structure in Complexity Theory Conference, pages 82--95. IEEE, 1993.
• 8: Jean Bourgain. Estimation of certain exponential sums arising in complexity theory. C. R. Math. Acad. Sci. Paris, 340(9):627--631, 2005.
• 9: Ido Ben-Eliezer, Rani Hod, and Shachar Lovett. Random low degree polynomials are hard to approximate. Manuscript, 2008.
• 10: Nayantara Bhatnagar , Parikshit Gopalan , Richard J. Lipton, Symmetric polynomials over Zm and simultaneous communication protocols, Journal of Computer and System Sciences, v.72 n.2, p.252-285, March 2006 [doi>10.1016/j.jcss.2005.06.007]
• 11: Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P=?NP question. SIAM J. Comput., 4(4):431--442, 1975.
• 12: László Babai , Noam Nisan , Márió Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs, Journal of Computer and System Sciences, v.45 n.2, p.204-232, Oct. 1992 [doi>10.1016/0022-0000(92)90047-M]
• 13: Ravi B. Boppana , Michael Sipser, The complexity of finite functions, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 14: Eli Ben-Sasson , Madhu Sudan , Salil Vadhan , Avi Wigderson, Randomness-efficient low degree tests and short PCPs via epsilon-biased sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780631]
• 15: Andrej Bogdanov , Emanuele Viola, Pseudorandom Bits for Polynomials, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.41-51, October 21-23, 2007 [doi>10.1109/FOCS.2007.56]
• 16: Arkadev Chattopadhyay, Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.449-458, October 21-23, 2007 [doi>10.1109/FOCS.2007.24]
• 17: Jin-Yi Cai, Frederic Green, and Thomas Thierauf. On the correlation of symmetric functions. Mathematical Systems Theory, 29(3):245--258, 1996.
• 18: Peter Clote and Evangelos Kranakis. Boolean Functions and Computation Models. Springer, 2002.
• 19: Fan R. K. Chung , Prasad Tetali, Communication complexity and quasi randomness, SIAM Journal on Discrete Mathematics, v.6 n.1, p.110-125, Feb. 1993 [doi>10.1137/0406009]
• 20: Thomas M. Cover , Joy A. Thomas, Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing), Wiley-Interscience, 2006
• 21: Devdatt Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomised algorithms, 2005. http://www.dsi.uniroma1.it/~ale/papers.html.
• 22: Yoav Freund, Boosting a weak learning algorithm by majority, Information and Computation, v.121 n.2, p.256-285, Sept. 1995 [doi>10.1006/inco.1995.1136]
• 23: W. T. Gowers. A new proof of Szemerédi's theorem for arithmetic progressions of length four. Geom. Funct. Anal., 8(3):529--551, 1998.
• 24: W. T. Gowers. A new proof of Szemerédi's theorem. Geom. Funct. Anal., 11(3):465--588, 2001.
• 25: Frederic Green, The correlation between parity and quadratic polynomials mod 3, Journal of Computer and System Sciences, v.69 n.1, p.28-44, August 2004 [doi>10.1016/j.jcss.2004.01.003]
• 26: Vince Grolmusz, Separating the communication complexities of MOD m and MOD p circuits, Journal of Computer and System Sciences, v.51 n.2, p.307-313, Oct. 1995 [doi>10.1006/jcss.1995.1069]
• 27: Mikael Goldmann, Johan Håstad, and Alexander A. Razborov. Majority gates vs. general weighted threshold gates. Computational Complexity, 2:277--300, 1992.
• 28: Oded Goldreich, Noam Nisan, and Avi Wigderson. On Yao's XOR lemma. Technical Report TR95-050, Electronic Colloquium on Computational Complexity, March 1995. www.eccc.uni-trier.de/.
• 29: Andrew Granville and Zeév Rudnick. Uniform distribution. In Equidistribution in Number Theory, An Introduction, volume 237 of NATO Science Series II: Mathematics, Physics and Chemistry, pages 1--13. Springer, 2007.
• 30: Frederic Green and Amitabha Roy. Uniqueness of optimal mod 3 circuits for parity. In Dagstuhl Seminar Proceedings, Algebraic Methods in Computational Complexity, volume 07411, 2007.
• 31: Frederic Green, Amitabha Roy, and Howard Straubing. Bounds on an exponential sum arising in Boolean circuit complexity. C. R. Math. Acad. Sci. Paris, 341(5):279--282, 2005.
• 32: Anna Gál and Vladimir Trifonov. On the correlation between parity and modular polynomials. In 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 4162 of Lecture Notes in Computer Science, pages 387--398. Springer, 2006.
• 33: Ben Green and Terence Tao. The distribution of polynomials over finite fields, with applications to the Gowers norms, 2007. arXiv:0711.3191v1.
• 34: Ben Green and Terence Tao. An inverse theorem for the Gowers U³ (G)norm. Proceedings of the Edinburgh Mathematical Society (Series 2), 51(01):73--153, 2008.
• 35: Dan Gutfreund and Emanuele Viola. Fooling parity tests with parity gates. In 8th International Workshop on Randomization and Computation (RANDOM), Lecture Notes in Computer Science, Volume 3122, pages 381--392. Springer, 2004.
• 36: Kristoffer Arnsfelt Hansen. Lower bounds for circuits with few modular gates using exponential sums. Electronic Colloquium on Computational Complexity, Technical Report TR06-079, 2006. www.eccc.uni-trier.de/.
• 37: Johan Håstad, Computational limitations of small-depth circuits, MIT Press, Cambridge, MA, 1987
• 38: Alexander D. Healy, Randomness-Efficient Sampling within NC1, Computational Complexity, v.17 n.1, p.3-37, April 2008 [doi>10.1007/s00037-007-0238-5]
• 39: Johan Håstad and Mikael Goldmann. On the power of small-depth threshold circuits. Comput. Complexity, 1(2):113--129, 1991.
• 40: András Hajnal , Wolfgang Maass , Pavel Pudlák , György Turán , Márió Szegedy, Threshold circuits of bounded depth, Journal of Computer and System Sciences, v.46 n.2, p.129-154, April 1993 [doi>10.1016/0022-0000(93)90001-D]
• 41: Alexander Healy and Emanuele Viola. Constant-depth circuits for arithmetic in finite fields of characteristic two. In 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, Volume 3884, pages 672--683. Springer, 2006.
• 42: Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
• 43: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 44: Shachar Lovett, Unconditional pseudorandom generators for low degree polynomials, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374455]
• 45: Shachar Lovett , Roy Meshulam , Alex Samorodnitsky, Inverse conjecture for the gowers norm is false, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374454]
• 46: Michael Luby, Boban Velickovic, and Avi Wigderson. Deterministic approximate counting of depth-2 circuits. In 2nd Israeli Symposium on Theoretical Computer Science (ISTCS), pages 18--24, 1993.
• 47: Valery A. Nepomnjascii. Rudimentary predicates and Turing calculations. Soviet Mathematics-Doklady, 11(6):1462--1465, 1970.
• 48: Noam Nisan. Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63--70, 1991.
• 49: Joseph (Seffi) Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 50: Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
• 51: Ran Raz, The BNS-chung criterion for multi-party communication complexity, Computational Complexity, v.9 n.2, p.113-122, April 01, 2000 [doi>10.1007/PL00001602]
• 52: Alexander Razborov. Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Mat. Zametki, 41(4):598--607, 623, 1987.
• 53: Alexander A. Razborov , Steven Rudich, Natural proofs, Journal of Computer and System Sciences, v.55 n.1, p.24-35, Aug. 1997 [doi>10.1006/jcss.1997.1494]
• 54: Alexander Razborov , Avi Wigderson, n&OHgr;(logn) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom, Information Processing Letters, v.45 n.6, p.303-307, April 16, 1993 [doi>10.1016/0020-0190(93)90041-7]
• 55: Alex Samorodnitsky, Low-degree tests at large distances, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250864]
• 56: R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]
• 57: Ronen Shaltiel , Emanuele Viola, Hardness amplification proofs require majority, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374461]
• 58: Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In 6th Symposium on Mathematical Foundations of Computer Science, volume 53 of Lecture Notes in Computer Science, pages 162--176. Springer, 1977.
• 59: Emanuele Viola , Salil P. Vadhan, The complexity of hardness amplification and derandomization, Harvard University, Cambridge, MA, 2006
• 60: Emanuele Viola. New correlation bounds for GF(2) polynomials using Gowers uniformity. Electronic Colloquium on Computational Complexity, Technical Report TR06-097, 2006. www.eccc.uni-trier.de/.
• 61: Emanuele Viola, Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates, SIAM Journal on Computing, v.36 n.5, p.1387-1403, December 2006 [doi>10.1137/050640941]
• 62: Emanuele Viola, The Sum of d Small-Bias Generators Fools Polynomials of Degree d, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.124-127, June 22-26, 2008 [doi>10.1109/CCC.2008.16]
• 63: Emanuele Viola and Avi Wigderson. Norms, XOR lemmas, and lower bounds for GF(2) polynomials and multiparty protocols. Theory of Computing, 4:137--168, 2008.

INDEX TERMS

Primary Classification:
  A. General Literature
  A.0 GENERAL

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms, Design, Theory