A strong direct product theorem for disjointness

ABSTRACT

A strong direct product theorem states that if we want to compute k independent instances of a function, using less than k times the resources needed for one instance, then the overall success probability will be exponentially small in k. We establish such a theorem for the randomized communication complexity of the Disjointness problem, i.e., with communication const• kn the success probability of solving k instances of size n can only be exponentially small in k. This solves an open problem of [KSW07, LSS08]. We also show that this bound even holds for $AM$-communication protocols with limited ambiguity. The main result implies a new lower bound for Disjointness in a restricted 3-player NOF protocol, and optimal communication-space tradeoffs for Boolean matrix product. Our main result follows from a solution to the dual of a linear programming problem, whose feasibility comes from a so-called Intersection Sampling Lemma that generalizes a result by Razborov [Raz92].

References

1. S. Aaronson and A. Ambainis. Quantum search of spatial regions. In Proceedings of 44th IEEE FOCS, pages 200--209, 2003. quant-ph/0303041.
2. K. Abrahamson. A time-space tradeoff for Boolean matrix multiplication. In Proceedings of 31st IEEE FOCS, pages 412--419, 1990.
3. Andris Ambainis, Robert Spalek, Ronald de Wolf. A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs. In Algorithmica, 55(3): 422--461, 2009.
4. L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory. In Proceedings of 27th IEEE FOCS, pages 337--347, 1986.
5. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar. An information statistics approach to data stream and communication complexity. In J. Comput. Syst. Sci., 68(4): 702--772, 2004.
6. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to Compress Interactive Communication. In STOC 2010.
7. P. Beame, M. Tompa, and P. Yan. Communication-space tradeoffs for unrestricted protocols. SIAM Journal on Computing, 23(3):652--661, 1994.
8. Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson. A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. In Computational Complexity, 15(4): 391--432, 2006.
9. Avraham Ben-Aroya, Oded Regev, Ronald de Wolf. A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs. In FOCS 2008, pages 477--486, 2008.
10. A. Chattopadhyay, A. Ada. Multiparty Communication Complexity of Disjointness. ECCC Technical Report 15(002), 2008.
11. R. Impagliazzo, R. Jaiswal, V. Kabanets, A. Wigderson. Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. In: STOC 2008, pages 579--588, 2008.
12. Rahul Jain, Hartmut Klauck, Ashwin Nayak. Direct product theorems for classical communication complexity via subdistribution bounds. In: STOC 2008, pages 599--608, 2008.
13. Rahul Jain, Hartmut Klauck. The Partition Bound for Classical Communication Complexity and Query Complexity. To appear in IEEE Conference on Computational Complexity 2010. See arXiv:0910.4266.
14. T. S. Jayram, Ravi Kumar, D. Sivakumar. Two applications of information complexity. In STOC 2003, pages 673--682, 2003.
15. B. Kalyanasundaram and G. Schnitger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545--557, 1992.
16. Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson. Non-Deterministic Communication Complexity with Few Witnesses. In J. Comput. Syst. Sci., 49(2): 247--257, 1994.
17. Mauricio Karchmer, Eyal Kushilevitz, Noam Nisan. Fractional Covers and Communication Complexity. In SIAM J. Discrete Math., 8(1): 76--92, 1995.
18. Hartmut Klauck. Rectangle Size Bounds and Threshold Covers in Communication Complexity. In: IEEE Conference on Computational Complexity 2003, pages 118--134, 2003.
19. Hartmut Klauck. Quantum and Classical Communication-Space Tradeoffs from Rectangle Bounds. In FSTTCS 2004, pages 384--395, 2004.
20. Hartmut Klauck. Lower Bounds for Quantum Communication Complexity. SIAM J. Comput., 37(1): 20--46, 2007.
21. Hartmut Klauck, Robert Spalek, Ronald de Wolf. Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. In SIAM J. Comput., 36(5): 1472--1493, 2007.
22. E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997.
23. T.W. Lam, P. Tiwari, and M. Tompa. Trade-offs between communication and space. Journal of Computer and Systems Sciences, 45(3):296--315, 1992. Earlier version in STOC'89.
24. Troy Lee, Adi Shraibman, Robert Spalek. A Direct Product Theorem for Discrepancy. IEEE Conference on Computational Complexity, pages 71--80, 2008.
25. Troy Lee, Adi Shraibman. Disjointness is Hard in the Multiparty Number-on-the-Forehead Model. Computational Complexity, 18(2): 309--336, 2009.
26. Nati Linial, Adi Shraibman. Lower bounds in communication complexity based on factorization norms. Random Struct. Algorithms, 34(3), pages 368--394, 2009.
27. L. Lovász. Communication Complexity: A Survey. In Paths, Flows, and VLSI Layout, edited by B. H. Korte, Springer, 1990.
28. N. Nisan, S. Rudich, and M. Saks. Products and help bits in decision trees. In Proceedings of 35th FOCS, pages 318--329, 1994.
29. N. Nisan and M. Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4(4):301--313, 1994. Earlier version in STOC'92.
30. I. Parnafes, R. Raz, and A. Wigderson. Direct product results and the GCD problem, in old and new communication models. In Proceedings of 29th ACM STOC, pages 363--372, 1997.
31. A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106(2):385--390, 1992.
32. A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya of the Russian Academy of Science, mathematics, 67(1):159--176, 2003. quant-ph/0204025.
33. R. Shaltiel. Towards proving strong direct product theorems. In Proceedings of 16th IEEE Conference on Computational Complexity, pages 107--119, 2001.
34. Alexander A. Sherstov. The pattern matrix method for lower bounds on quantum communication. STOC 2008, pages 85--94, 2008.
35. Falk Unger. A Probabilistic Inequality with Applications to Threshold Direct-product Theorems. FOCS 2009, 2009.
36. E. Viola and A. Wigderson. One-way multi-party communication lower bound for pointer jumping with applications. In: Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, 2007.
37. Emanuele Viola, Avi Wigderson. Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. In Theory of Computing 4(1): 137--168, 2008.
38. A. C-C. Yao. Some Complexity Questions Related to Distributive Computing. In Proceedings of STOC 1979, pages 209--213, 1979.
39. A. C-C. Yao. Theory and applications of trapdoor functions. In Proceedings of 23rd IEEE FOCS, pages 80--91, 1982.
40. C-C. Yao. Lower Bounds by Probabilistic Arguments. 24th IEEE Symp. Foundations of Computer Science, pp. 420--428, 1983.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Cellular architectures

• Hardware

  • Emerging technologies

    • Quantum technologies

      • Quantum dots and cellular automata

• Theory of computation

  • Design and analysis of algorithms

  • Models of computation