[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].

[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 Z_m and MOD_q. 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 U³ 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 mod m and mod 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 NC¹. 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].

[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.