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]