Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols

by Emanuele Viola and Avi Wigderson

Theory of Computing, Volume 4(7), pp. 137-168, 2008

Bibliography with links to cited articles

[1] 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. [Wiley:10.1002/rsa.3240030308].
[2] Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron: Testing low-degree polynomials over GF(2). In Approximation, randomization, and combinatorial optimization, volume 2764 of LNCS, pp. 188-199. Springer-Verlag, Berlin, 2003. [Springer:5pcg1j8cfl39tmpy].
[3] László Babai, Anna Gál, Peter G. Kimmel, and Satyanarayana V. Lokam: Communication complexity of simultaneous messages. SIAM J. Comput., 33(1):137-166, 2003. [SICOMP:10.1137/S0097539700375944].
[4] László Babai, Thomas P. Hayes, and Peter G. Kimmel: The cost of the missing bit: communication complexity with help. Combinatorica, 21(4):455-488, 2001. [doi:10.1007/s004930100009]. [ DOI ]
[5] László Babai, Noam Nisan, and Márió Szegedy: Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. System Sci., 45(2):204-232, 1992. [JCSS:10.1016/0022-0000(92)90047-M].
[6] Jean Bourgain: Estimation of certain exponential sums arising in complexity theory. C. R. Math., 340(9):627-631, 2005. [Elsevier:10.1016/j.crma.2005.03.008].
[7] Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton: Multi-party protocols. In Proc. 15th STOC, pp. 94-99, Boston, Massachusetts, 1983. ACM Press. [STOC:800061.808737].
[8] Arkadev Chattopadhyay: An improved bound on correlation between polynomials over Zm and MODq. Technical Report TR06-107, Electronic Colloquium on Computational Complexity, 2006. [ECCC:TR06-107].
[9] Fan R. K. Chung and Prasad Tetali: Communication complexity and quasi randomness. SIAM J. Discrete Math., 6(1):110-123, 1993. [SIDMA:10.1137/0406009].
[10] Uri Feige: Error reduction by parallel repetition-the state of the art. Technical report, Weizmann Science Press of Israel, Jerusalem, Israel, 1995.
[11] Lance Fortnow: Complexity-theoretic aspects of interactive proof systems. PhD thesis, Massachusetts Institute of Technology, 1989. Tech Report MIT/LCS/TR-447.
[12] Oded Goldreich and Leonid A. Levin: A hard-core predicate for all one-way functions. In Proc. 21st STOC, pp. 25-32, New York, 1989. ACM Press. [STOC:73007.73010].
[13] Oded Goldreich, Noam Nisan, and Avi Wigderson: On Yao's XOR lemma. Technical Report TR95-050, Electronic Colloquium on Computational Complexity, March 1995. [ECCC:TR95-050].
[14] 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. [Springer:lg2rlw8pvtt2x0qj].
[15] W. T. Gowers: A new proof of Szemerédi's theorem. Geom. Funct. Anal., 11(3):465-588, 2001. [Springer:00622770r8437760].
[16] Ben Green and Terence Tao: An inverse theorem for the gowers U3 norm, 2005. arXiv.org:math/0503014. [arXiv:math/0503014].
[17] Frederic Green, Amitabha Roy, and Howard Straubing: Bounds on an exponential sum arising in Boolean circuit complexity. C. R. Math., 341(5):279-282, 2005. [Elsevier:10.1016/j.crma.2005.07.011].
[18] Vince Grolmusz: Separating the communication complexities of m and p circuits. J. Comput. System Sci., 51(2):307-313, 1995. [JCSS:10.1006/jcss.1995.1069].
[19] Dan Gutfreund and Emanuele Viola: Fooling parity tests with parity gates. In Proc. 8th Intern. Workshop on Randomization and Computation (RANDOM'08), volume 3122 of LNCS, pp. 381-392. Springer-Verlag, 2004. [Springer:x9px6h8l0tb6et6b].
[20] András Hajnal, Wolfgang Maass, Pavel Pudlák, Márió Szegedy, and György Turán: Threshold circuits of bounded depth. J. Comput. System Sci., 46(2):129-154, 1993. [JCSS:10.1016/0022-0000(93)90001-D].
[21] Johan Håstad and Mikael Goldmann: On the power of small-depth threshold circuits. Comput. Complexity, 1(2):113-129, 1991. [CC:r0mv45x710nn1q76].
[22] Alexander Healy: Randomness-efficient sampling within NC1. In Proceedings of the 10th International Workshop on Randomization and Computation (RANDOM'06), volume 4110 of LNCS, pp. 398-409. Springer-Verlag, 2006. [Springer:b773545612310728].
[23] Russell Impagliazzo: Hard-core distributions for somewhat hard problems. In Proc. 36th FOCS, pp. 538-545, Los Alamitos, CA, USA, 1995. IEEE Computer Society. [FOCS:10.1109/SFCS.1995.492584].
[24] Russell Impagliazzo and Avi Wigderson: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proc. 29th STOC, pp. 220-229, New York, 1997. ACM Press. [STOC:258533.258590].
[25] Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, and David Zuckerman: Testing low-degree polynomials over prime fields. In Proc. 45th FOCS, pp. 423-432, Los Alamitos, CA, USA, 2004. IEEE Computer Society. [FOCS:10.1109/FOCS.2004.64].
[26] Eyal Kushilevitz and Noam Nisan: Communication complexity. Cambridge University Press, Cambridge, 1997.
[27] Leonid A. Levin: One way functions and pseudorandom generators. Combinatorica, 7(4):357-363, 1987. [Springer:e1415188r28663m5].
[28] Michael Luby, Boban Velickovic, and Avi Wigderson: Deterministic approximate counting of depth-2 circuits. In Proc. 2nd Israeli Symp. on Theoretical Computer Science (ISTCS'93), pp. 18-24, Los Alamitos, CA, USA, 1993. IEEE Computer Society.
[29] J. Naor and M. Naor: Small-bias probability spaces: efficient constructions and applications. In Proc. 22nd STOC, pp. 213-223. ACM Press, 1990. [STOC:100216.100244].
[30] Noam Nisan: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63-70, 1991. [Springer:g79x907l52546012].
[31] Noam Nisan, Steven Rudich, and Michael Saks: Products and help bits in decision trees. SIAM J. Comput., 28(3):1035-1050, 1999. [SICOMP:10.1137/S0097539795282444].
[32] Noam Nisan and Avi Wigderson: Hardness vs. randomness. J. Comput. System Sci., 49(2):149-167, October 1994. [JCSS:10.1016/S0022-0000(05)80043-1].
[33] Itzhak Parnafes, Ran Raz, and Avi Wigderson: Direct product results and the GCD problem, in old and new communication models. In Proc. 29th STOC, pp. 363-372, New York, 1997. ACM Press. [STOC:258533.258620].
[34] Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. [SICOMP:10.1137/S0097539795280895].
[35] Ran Raz: The BNS-Chung criterion for multi-party communication complexity. Comput. Complexity, 9(2):113-122, 2000. [CC:u8q21j1ccvltrb40].
[36] Alexander A. 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.
[37] Alex Samorodnitsky: Low-degree tests at large distances. In Proc. 39th STOC, pp. 506-515, New York, 2007. ACM Press. [STOC:1250790.1250864].
[38] Alex Samorodnitsky and Luca Trevisan: Gowers uniformity, influence of variables, and PCPs. In Proc. 38th STOC, pp. 11-20, New York, May 2006. ACM Press. [STOC:1132516.1132519].
[39] Ronen Shaltiel: Towards proving strong direct product theorems. Comput. Complexity, 12(1-2):1-22, 2003. [CC:ku74rl1ga9te5lpe].
[40] Ronen Shaltiel and Christopher Umans: Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM, 52(2):172-216, 2005. [JACM:1059513.1059516].
[41] Ronen Shaltiel and Emanuele Viola: Hardness amplification proofs require majority. In Proc. 40th STOC, pp. 589-598, Victoria, Canada, 2008. ACM Press. [STOC:1374376.1374461].
[42] Roman Smolensky: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proc. 19th STOC, pp. 77-82, New York, 1987. ACM Press. [STOC:28395.28404].
[43] Emanuele Viola: New correlation bounds for GF(2) polynomials using Gowers uniformity. Technical Report TR06-097, Electronic Colloquium on Computational Complexity, 2006. [ECCC:TR06-097].
[44] Emanuele Viola: Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM J. Comput., 36(5):1387-1403, 2007. [SICOMP:10.1137/050640941]. [ http ]
[45] Andrew Chi-Chih Yao: Some complexity questions related to distributive computing. In Proc. 11th STOC, pp. 209-213, New York, 1979. ACM Press. [STOC:800135.804414].
[46] Andrew Chi-Chih Yao: Theory and applications of trapdoor functions (extended abstract). In Proc. 23rd FOCS, pp. 80-91, Los Alamitos, CA, USA, 1982. IEEE Computer Society.

This file has been generated by bibtex2html 1.85.