A Communication Game Related to the Sensitivity Conjecture
by Justin Gilmer, Michal Koucký, and Michael Saks
Theory of Computing, Volume 13(7), pp. 1-18, 2017
Bibliography with links to cited articles
[1] Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs: Separations in query complexity based on pointer functions. In Proc. 48th STOC, pp. 800–813. ACM Press, 2016. Version at ECCC. [doi:10.1145/2897518.2897524, arXiv:1506.04719]
[2] Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, and Song Zuo: Tighter relations between sensitivity and other complexity measures. In Proc. 41st Internat. Colloq. on Automata, Languages and Programming (ICALP’14), volume 8572 of LNCS, pp. 101–113. Springer, 2014. Version at ECCC. [doi:10.1007/978-3-662-43948-7_9, arXiv:1411.3419]
[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. Preliminary version in FOCS’98. [doi:10.1145/502090.502097, arXiv:quant-ph/9802049]
[4] 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]
[5] Thomas Cover and Joy Thomas: Elements of Information Theory. John Wiley & Sons, Inc., 2012.
[6] Andrew Drucker: A note on a communication game, 2017. [arXiv:1706.07890]
[7] Justin Gilmer, Michal Koucký, and Michael Saks: A new approach to the sensitivity conjecture. In Proc. 9th Internat. Conf. on Information Communication Technology and Systems (ITCS’15), pp. 247–254. ACM Press, 2015. [doi:10.1145/2688073.2688096]
[8] Justin Gilmer, Michael Saks, and Srikanth Srinivasan: Composition limits and separating examples for some boolean function complexity measures. Combinatorica, 36(3):265–311, 2016. Preliminary version in CCC’13. [doi:10.1007/s00493-014-3189-x, arXiv:1306.0630]
[9] Pooya Hatami, Raghav Kulkarni, and Denis Pankratov: Variations on the Sensitivity Conjecture. Number 4 in Graduate Surveys. Theory of Computing Library, 2011, pp. 1–27. [doi:10.4086/toc.gs.2011.004]
[10] Claire Kenyon and Samuel Kutin: Sensitivity, block sensitivity, and ℓ-block sensitivity of Boolean functions. Inform. and Comput., 189(1):43–53, 2004. [doi:10.1016/j.ic.2002.12.001]
[11] László Lovász and Neal E. Young: Lecture notes on evasiveness of graph properties, 2002. [arXiv:cs/0205031]
[12] Gatis Midrijanis: Exact quantum query complexity for total Boolean functions, 2004. [arXiv:quant-ph/0403168]
[13] Noam Nisan: CREW PRAMs and decision trees. SIAM J. Comput., 20(6):999–1007, 1991. Preliminary version in STOC’89. [doi:10.1137/0220062]
[14] Noam Nisan and Mario Szegedy: On the degree of Boolean functions as real polynomials. Comput. Complexity, 4(4):301–313, 1994. Preliminary version in STOC’92. [doi:10.1007/BF01263419]
[15] Mario Szegedy: An O(n0.4732) upper bound on the complexity of the GKS communication game, 2015. [arXiv:1506.06456]