Variations on the Sensitivity Conjecture
by Pooya Hatami, Raghav Kulkarni, and Denis Pankratov
Theory of Computing, Graduate Surveys 4, pp. 1-27, 2011
Bibliography with links to cited articles
[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 L1 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 NPA ∩coNPA from PA 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]