[1]   Scott Aaronson: Quantum certificate complexity. In Proc. 18th IEEE Conf. Comp. Compl. (CCC), pp. 171–178. IEEE Comp. Soc. Press, 2003. [doi:10.1109/CCC.2003.1214418]

[2]   Scott Aaronson: The “sensitivity” of 2-colorings of the d-dimensional integer lattice. http://mathoverflow.net/questions/31482/, July 2010.

[3]   Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf: Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. [doi:10.1145/502090.502097]

[4]   Manuel Blum and Russell Impagliazzo: Generic oracles and oracle classes. In Proc. 28th FOCS, pp. 118–126. IEEE Comp. Soc. Press, 1987. [doi:10.1109/SFCS.1987.30]

[5]   Siegfried Bublitz, Ute Schürfeld, Ingo Wegener, and Bernd Voigt: Properties of complexity measures for PRAMs and WRAMs. Theoret. Comput. Sci., 48(1):53–73, 1986. [doi:10.1016/0304-3975(86)90083-6]

[6]   Harry Buhrman and Ronald de Wolf: Complexity measures and decision tree complexity: A survey. Theoret. Comput. Sci., 288(1):21–43, 2002. [doi:10.1016/S0304-3975(01)00144-X]

[7]   Sourav Chakraborty: On the sensitivity of cyclically-invariant Boolean functions. In Proc. 20th Ann. IEEE Conf. Comput. Complexity (CCC), pp. 163–167. IEEE Comp. Soc. Press, 2005. [doi:10.1109/CCC.2005.38]

[8]   Sourav Chakraborty: Sensitivity, block sensitivity and certificate complexity of Boolean functions. Master’s thesis, University of Chicago, USA, 2005.

[9]   Fan R. K. Chung, Zoltán Füredi, Ronald L. Graham, and Paul Seymour: On induced subgraphs of the cube. J. Combin. Theory Ser. A, 49(1):180–187, 1988. [doi:10.1016/0097-3165(88)90034-9]

[10]   Stephen Cook and Cynthia Dwork: Bounds on the time for parallel RAM’s to compute simple functions. In Proc. 14th STOC, pp. 231–233, New York, NY, USA, 1982. ACM Press. [doi:10.1145/800070.802196]

[11]   Jürgen Forster: A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. System Sci., 65:612–625, December 2002. [doi:10.1016/S0022-0000(02)00019-3]

[12]   Ehud Friedgut and Gil Kalai: Every monotone graph property has a sharp threshold. Proc. AMS, 124(10):2993–3002, 1996. [doi:10.1090/S0002-9939-96-03732-X]

[13]   Craig Gotsman and Nathan Linial: The equivalence of two problems on the cube. J. Combin. Theory Ser. A, 61(1):142–146, 1992. [doi:10.1016/0097-3165(92)90060-8]

[14]   Vince Grolmusz: On the power of circuits with gates of low L₁ norms. Theoret. Comput. Sci., 188(1–2):117–128, 1997. [doi:10.1016/S0304-3975(96)00290-3]

[15]   Juris Hartmanis and Lane A. Hemachandra: One-way functions, robustness and the non-isomorphism of NP-complete sets. In Proc. 2nd IEEE Struct. Complex. Theory Conf., pp. 160–174. IEEE Comp. Soc. Press, 1987.

[16]   Bala Kalyanasundaram and Georg Schintger: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math., 5:545–557, 1992. [doi:10.1137/0405044]

[17]   Claire Kenyon and Sandy Kutin: Sensitivity, block sensitivity, and l-block sensitivity of Boolean functions. Inform. and Comput., 189(1):43, 2004. [doi:10.1016/j.ic.2002.12.001]

[18]   Eyal Kushilevitz and Noam Nisan: Communication Complexity. Cambridge University Press, 1997.

[19]   László Lovász and Michael Saks: Communication complexity and combinatorial lattice theory. J. Comput. System Sci., 47(2):322–349, 1993. [doi:10.1016/0022-0000(93)90035-U]

[20]   Kurt Mehlhorn and Erik M. Schmidt: Las Vegas is better than determinism in VLSI and distributed computing. In Proc. 14th STOC, pp. 330–337, New York, NY, USA, 1982. ACM Press. [doi:10.1145/800070.802208]

[21]   Gatis Midrijanis: Exact quantum query complexity for total Boolean functions. Technical report, Cornell University ArXiv.org, 2004. [arXiv:quant-ph/0403168]

[22]   Ilan Newman: Private vs. common random bits in communication complexity. Inform. Process. Lett., 39:67–71, July 1991. [doi:10.1016/0020-0190(91)90157-D]

[23]   Noam Nisan: CREW PRAMs and decision trees. In Proc. 21st STOC, pp. 327–335, New York, NY, USA, 1989. ACM Press. [doi:10.1145/73007.73038]

[24]   Noam Nisan and Mario Szegedy: On the degree of Boolean functions as real polynomials. Comput. Complexity, 4:462–467, 1992. [doi:10.1007/BF01263419]

[25]   Noam Nisan and Avi Wigderson: On rank vs. communication complexity. Combinatorica, 15:557–565, 1995. [doi:10.1007/BF01192527]

[26]   Ryan O’Donnell, John Wright, and Yuan Zhou: The Fourier entropy-influence conjecture for certain classes of Boolean functions. To appear in ICALP’11, 2011.

[27]   Ramamohan Paturi and Janos Simon: Probabilistic communication complexity. J. Comput. System Sci., 3(1):106–123, 1986. [doi:10.1016/0022-0000(86)90046-2]

[28]   Alexander A. Razborov: On the distributional complexity of disjointness. Theoret. Comput. Sci., 106:385–390, 1992. [doi:10.1016/0304-3975(92)90260-M]

[29]   Rüdiger Reischuk: A lower time-bound for parallel random access machines without simultaneous writes. Technical Report RJ3431, IBM, New York, 1982.

[30]   Ronald L. Rivest and Jean Vuillemin: On recognizing graph properties from adjacency matrices. Theoret. Comput. Sci., 3(3):371–384, 1976. [doi:10.1016/0304-3975(76)90053-0]

[31]   David Rubinstein: Sensitivity vs. block sensitivity of Boolean functions. Combinatorica, 15(2):297–299, 1995. [doi:10.1007/BF01200762]

[32]   Alexander Sherstov: On quantum-classical equivalence for composed communication problems. Quantum Inf. Comput., 10(5&6):435–455, 2010.

[33]   Yaoyun Shi: Approximating linear restrictions of Boolean functions. Technical report, Manuscript, 2002.

[34]   Hans-Ulrich Simon: A tight Ω(log log n)-bound on the time for parallel RAMs to compute non-degenerate Boolean functions. In Proc. 4th Int. Symp. Fundam. Comput. Theory (FCT), volume 158 of LNCS, pp. 439–444. Springer, 1983.

[35]   Gábor Tardos: Query complexity, or why is it difficult to separate NP^A ∩coNP^A from P^A by random oracles A? Combinatorica, 9:385–392, 1989. [doi:10.1007/BF02125350]

[36]   György Turán: The critical complexity of graph properties. Inform. Process. Lett., 18:151–153, 1984. [doi:10.1016/0020-0190(84)90019-X]

[37]   Ronald de Wolf: Quantum communication and complexity. Theoret. Comput. Sci., 287(1):337–353, 2002. [doi:10.1016/S0304-3975(02)00377-8]

[38]   Ronald de Wolf: A Brief Introduction to Fourier Analysis on the Boolean Cube. Theory Comput. Library, Grad. Surv., 1, 2008. [doi:10.4086/toc.gs.2008.001]

[39]   Andrew Chi-Chih Yao: Some complexity questions related to distributive computing. In Proc. 11th STOC, pp. 209–213, New York, NY, USA, 1979. ACM Press. [doi:10.1145/800135.804414]

[40]   Zhiqiang Zhang and Yaoyun Shi: On the parity complexity measures of Boolean functions. Theoret. Comput. Sci., 411(26–28):2612–2618, 2010. [doi:10.1016/j.tcs.2010.03.027]