The Influence Lower Bound Via Query Elimination

by Rahul Jain and Shengyu Zhang

Theory of Computing, Volume 7(10), pp. 147-153, 2011

Bibliography with links to cited articles

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

[2]   Amit Chakrabarti and Subhash Khot: Improved lower bounds on the randomized complexity of graph properties. In Proc. 28th Intern. Colloq. Autom. Lang. Program. (ICALP), number 2076 in Lecture Notes in Comput. Sci., pp. 285–296. Springer, 2001. [doi:10.1007/3-540-48224-5_24]

[3]   Amit Chakrabarti and Oded Regev: An optimal lower bound on the communication complexity of Gap-Hamming-Distance. In Proc. 43th STOC, pp. 51–60. ACM Press, 2011. [doi:10.1145/1993636.1993644]

[4]   Ronald de Wolf: A Brief Introduction to Fourier Analysis on the Boolean Cube. Number 1 in Graduate Surveys. Theory of Computing Library, 2008. [doi:10.4086/]

[5]   Péter Hajnal: An Ω(n4/3) lower bound on the randomized complexity of graph properties. Combinatorica, 11(2):131–143, 1991. [doi:10.1007/BF01206357]

[6]   Rahul Jain and Hartmut Klauck: The partition bound for classical communication complexity and query complexity. In Proc. 25th IEEE Conf. Comput. Complexity (CCC), pp. 247–258. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.31]

[7]   Hartmut Klauck: Lower bounds for quantum communication complexity. SIAM J. Comput., 1:20–46, 2007. [doi:10.1137/S0097539702405620]

[8]   Hartmut Klauck: A strong direct product theorem for Disjointness. In Proc. 42nd STOC, pp. 77–86. ACM Press, 2010. [doi:10.1145/1806689.1806702]

[9]   Homin Lee: Decision trees and influence: An inductive proof of the OSSS inequality. Theory of Computing, 6(1):81–84, 2010. [doi:10.4086/toc.2010.v006a004]

[10]   Troy Lee and Shengyu Zhang: Composition theorems in communication complexity. In Proc. 37th Intern. Colloq. Autom. Lang. Program. (ICALP), number 6198 in Lecture Notes in Comput. Sci., pp. 475–489. Springer, 2010. [doi:10.1007/978-3-642-14165-2_41]

[11]   Ryan O’Donnell: Some topics in analysis of Boolean functions. In Proc. 40th STOC, pp. 569–578. ACM Press, 2008. [doi:10.1145/1374376.1374458]

[12]   Ryan O’Donnell, Michael E. Saks, Oded Schramm, and Rocco A. Servedio: Every decision tree has an influential variable. In Proc. 46th FOCS, pp. 31–39. IEEE Comp. Soc. Press, 2005. [doi:10.1109/SFCS.2005.34]

[13]   Ryan O’Donnell and Rocco Servedio: Learning monotone decision trees in polynomial time. SIAM J. Comput., 37(3):827–844, 2007. [doi:10.1137/060669309]

[14]   Alexander Sherstov: The pattern matrix method for lower bounds on quantum communication. In Proc. 40th STOC, pp. 85–94. ACM Press, 2008. [doi:10.1145/1374376.1374392]

[15]   Yaoyun Shi and Yufan Zhu: The quantum communication complexity of block-composed functions. Quantum Inf. Comput., 9(5&6):444–460, 2009.,