SpringerLink
Log in

A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

A strong direct product theorem for a problem in a given model of computation states that, in order to compute k instances of the problem, if we provide resource which is less than k times the resource required for computing one instance of the problem with constant success probability, then the probability of correctly computing all the k instances together, is exponentially small in k. In this paper, we consider the model of two-party bounded-round public-coin randomized communication complexity. We show a direct product theorem for the communication complexity of any complete relation in this model. In particular, our result implies a strong direct product theorem for the two-party constant-round public-coin randomized communication complexity of all complete relations. As an immediate application of our result, we get a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. Our result generalizes the result of Jain which can be regarded as the special case when the number of messages is one. Our result can be considered as an important progress towards settling the strong direct product conjecture for two-party public-coin communication complexity, a major open question in this area. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used by Jain. One key tool used in our work and also by Jain is a message compression technique due to Braverman and Rao, who used it to show a direct sum theorem in the same model of communication complexity as considered by us. Another important tool that we use is a correlated sampling protocol which, for example, has been used by Holenstein for proving a parallel repetition theorem for two-prover games.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. When \(\mathrm {R}^{(t),\mathrm {pub}}_{\varepsilon }(f)\) is a constant, all the lower bounds are constants as well. It is known that several lower bounds satisfy a strong direct product theorem, such as conditional relative entropy [14]. Thus in this case a strong direct product result for the model we concerns follows directly.

  2. We justify here the composition of \(R_i\). Random variables \(D_{-i} U_{-i}\) are useful because conditioning on them makes the distribution of inputs product across Alice and Bob (for fixed values of \(X_iY_i\)). Random variables \(X_C Y_C\) are helpful since conditioning on them ensures that the inputs become product even when conditioned on success on C. Random variables \(X_{[i-1]} Y_{[i-1]}\) are helpful because we use the following chain rule to draw a new coordinate outside of C with low information.

    $$\begin{aligned} \mathrm {I}\,\left( XY \, \!: \, \!M \right) = \sum _i \mathrm {I}\,\left( X_iY_i \, \!: \, \!M \, \!\big \vert \, \!X_{[i-1]}Y_{[i-1]} \right) \end{aligned}$$

References

  1. Ambainis, A., Špalek, R., de Wolf, R.: A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs. Algorithmica 55(3), 422–461 (2009). doi:10.1007/s00453-007-9022-9

    Article  MathSciNet  MATH  Google Scholar 

  2. Bar-Yossef, Z., Jayram, T., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, FOCS ’02, pp. 209–218 (2002). doi:10.1109/SFCS.2002.1181944

  3. Barak, B., Braverman, M., Chen, X., Rao, A.: How to compress interactive communication. SIAM J. Comput. 42(3), 1327–1363 (2013). doi:10.1137/100811969

    Article  MathSciNet  MATH  Google Scholar 

  4. Ben-Aroya, A., Regev, O., de Wolf, R.: A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs. In: Proceedings of the 49rd Annual IEEE Symposium on Foundations of Computer Science, FOCS ’08, pp. 477–486 (2008). doi:10.1109/FOCS.2008.45

  5. Braverman, M., Rao, A.: Information equals amortized communication. IEEE Trans. Inf. Theory 60(10), 6058–6069 (2014). doi:10.1109/TIT.2014.2347282

    Article  MathSciNet  MATH  Google Scholar 

  6. Braverman, M., Rao, A., Weinstein, O., Yehudayoff, A.: Direct product via round-preserving compression. In: Automata, Languages, and Programming, Lecture Notes in Computer Science, vol. 7965, pp. 232–243. Springer, Berlin (2013). doi:10.1007/978-3-642-39206-1_20

  7. Braverman, M., Rao, A., Weinstein, O., Yehudayoff, A.: Direct products in communication complexity. In: Proceedings of the 54rd Annual IEEE Symposium on Foundations of Computer Science, FOCS ’13, pp. 746–755 (2013). doi:10.1109/FOCS.2013.85

  8. Braverman, M., Weinstein, O.: An interactive information odometer with applications. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing, STOC ’15, pp. 341–350 (2000). doi:10.1145/2746539.2746548

  9. Chakrabarti, A., Shi, Y., Wirth, A., Yao, A.: Informational complexity and the direct sum problem for simultaneous message complexity. In: Proceedings of the 42rd Annual IEEE Symposium on Foundations of Computer Science, FOCS ’01, pp. 270–278 (2001). doi:10.1109/SFCS.2001.959901

  10. Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. Wiley, London (2006)

    MATH  Google Scholar 

  11. Drucker, A.: Improved direct product theorems for randomized query complexity. Comput. Complex. 21(2), 197–244 (2012). doi:10.1007/s00037-012-0043-7

    Article  MathSciNet  MATH  Google Scholar 

  12. Holenstein, T.: Parallel repetition: simplification and the no-signaling case. Theory Comput. 5(8), 141–172 (2009). doi:10.4086/toc.2009.v005a008. http://www.theoryofcomputing.org/articles/v005a008

  13. Ibinson, B., Linden, N., Winter, A.: Robustness of quantum Markov chains. Commun. Math. Phys. 277(2), 289–304 (2008). doi:10.1007/s00220-007-0362-8

    Article  MathSciNet  MATH  Google Scholar 

  14. Jain, R.: New strong direct product results in communication complexity. Journal of the ACM (JACM), 62(3), (2015). doi:10.1145/2699432

  15. Jain, R., Klauck, H.: New results in the simultaneous message passing model via information theoretic techniques. In: Proceedings of the 24rd Annual IEEE Conference on Computational Complexity, CCC ’09, pp. 369–378 (2009). doi:10.1109/CCC.2009.28

  16. Jain, R., Klauck, H., Nayak, A.: Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract. In: Proceedings of the 40rd Annual ACM Symposium on Theory of Computing, STOC ’08, pp. 599–608 (2008). doi:10.1145/1374376.1374462

  17. Jain, R., Radhakrishnan, J., Sen, P.: The quantum communication complexity of the pointer chasing problem: the bit version. In: FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 2556, pp. 218–229. Springer, Berlin (2002). doi:10.1007/3-540-36206-1_20

  18. Jain, R., Radhakrishnan, J., Sen, P.: A direct sum theorem in communication complexity via message compression. In: Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 2719, pp. 300–315. Springer, Berlin (2003). doi:10.1007/3-540-45061-0_26

  19. Jain, R., Radhakrishnan, J., Sen, P.: A lower bound for the bounded round quantum communication complexity of set disjointness. In: Proceedings of the 44rd Annual IEEE Symposium on Foundations of Computer Science, FOCS ’03, pp. 220–229 (2003). doi:10.1109/SFCS.2003.1238196

  20. Jain, R., Radhakrishnan, J., Sen, P.: Prior entanglement, message compression and privacy in quantum communication. In: Proceedings of the 20rd Annual IEEE Conference on Computational Complexity, CCC ’05, pp. 285–296 (2005). doi:10.1109/CCC.2005.24

  21. Jain, R., Sen, P., Radhakrishnan, J.: Optimal direct sum and privacy trade-off results for quantum and classical communication complexity (2008). ar**v:0807.1267

  22. Jain, R., Yao, P.: A strong direct product theorem in terms of the smooth rectangle bound (2012). ar**v:1209.0263

  23. Klauck, H.: On quantum and probabilistic communication: Las Vegas and one-way protocols. In: Proceedings of the 32rd Annual ACM Symposium on Theory of Computing, STOC ’00, pp. 644–651 (2000). doi:10.1145/335305.335396

  24. Klauck, H.: A strong direct product theorem for disjointness. In: Proceedings of the 42rd ACM Symposium on Theory of Computing, STOC ’10, pp. 77–86 (2010). doi:10.1145/1806689.1806702

  25. Klauck, H., Nayak, A., Ta-Shma, A., Zuckerman, D.: Interaction in quantum communication and the complexity of set disjointness. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, STOC ’01, pp. 124–133 (2001). doi:10.1145/380752.380786

  26. Klauck, H., Špalek, R., de Wolf, R.: Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM J. Comput. 36(5), 1472–1493 (2007). doi:10.1137/05063235X

    Article  MathSciNet  MATH  Google Scholar 

  27. Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1996)

    Book  MATH  Google Scholar 

  28. Lee, T., Roland, J.: A strong direct product theorem for quantum query complexity. Comput. Complex. 22(2), 429–462 (2013). doi:10.1007/s00037-013-0066-8

    Article  MathSciNet  MATH  Google Scholar 

  29. Lee, T., Shraibman, A., Špalek, R.: A direct product theorem for discrepancy. In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC ’08, pp. 71–80 (2008). doi:10.1109/CCC.2008.25

  30. Nisan, N., Rudich, S., Saks, M.: Products and help bits in decision trees. SIAM J. Comput. 28(3), 1035–1050 (1999). doi:10.1137/S0097539795282444

    Article  MathSciNet  MATH  Google Scholar 

  31. Nisan, N., Widgerson, A.: Rounds in communication complexity revisited. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC ’91, pp. 419–429 (1991). doi:10.1145/103418.103463

  32. Parnafes, I., Raz, R., Wigderson, A.: Direct product results and the GCD problem, in old and new communication models. In: Proceedings of the 29rd Annual ACM Symposium on Theory of Computing, STOC ’97, pp. 363–372 (1997). doi:10.1145/258533.258620

  33. Ponzio, S.J., Radhakrishnan, J., Venkatesh, S.: The communication complexity of pointer chasing. J. Comput. Syst. Sci. 62(2), 323–355 (2001). doi:10.1006/jcss.2000.1731. http://www.sciencedirect.com/science/article/pii/S0022000000917318

  34. Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763–803 (1998). doi:10.1137/S0097539795280895

    Article  MathSciNet  MATH  Google Scholar 

  35. Razborov, A.: On the distributional complexity of disjointness. Theor. Comput. Sci. 106(2), 385–390 (1992). doi:10.1016/0304-3975(92)90260-M. http://www.sciencedirect.com/science/article/pii/030439759290260M

  36. Shaltiel, R.: Towards proving strong direct product theorems. Comput. Complex. 12(1–2), 1–22 (2003). doi:10.1007/s00037-003-0175-x

    Article  MathSciNet  MATH  Google Scholar 

  37. Shannon, C.E.: A mathematical theory of communication. SIGMOBILE Mob. Comput. Commun. Rev. 5(1), 3–55 (2001). doi:10.1145/584091.584093

    Article  MathSciNet  Google Scholar 

  38. Sherstov, A.A.: Strong direct product theorems for quantum communication and query complexity. SIAM J. Comput. 41(5), 1122–1165 (2012). doi:10.1137/110842661

    Article  MathSciNet  MATH  Google Scholar 

  39. Viola, E., Wigderson, A.: Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory Comput. 4(7), 137–168 (2008). doi:10.4086/toc.2008.v004a007. http://www.theoryofcomputing.org/articles/v004a007

  40. Yao, A.C.C.: Some complexity questions related to distributive computing (preliminary report). In: Proceedings of the 11rd Annual ACM Symposium on Theory of Computing, STOC ’79, pp. 209–213 (1979). doi:10.1145/800135.804414

  41. Yao, A.C.C.: Theory and application of trapdoor functions. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, FOCS ’82, pp. 80–91 (1982). doi:10.1109/SFCS.1982.45

Download references

Acknowledgments

This work is funded by the Singapore Ministry of Education, partly through the Academic Research Fund Tier3 MOE2012-T3-1-009 and partly through the internal Grants of the Center for Quantum Technologies, Singapore. We thank the referees for their helpful comments.

Author information

Authors and Affiliations

  1. Department of Computer Science, Centre for Quantum Technologies, National University of Singapore, Singapore, Singapore

    Rahul Jain

  2. MajuLab, CNRS-UNS-NUS-NTU International Joint Research Unit, UMI 3654, Singapore, Singapore

    Rahul Jain

  3. Centre for Quantum Technologies, National University of Singapore, Singapore, Singapore

    Attila Pereszlényi & Penghui Yao

Authors
  1. Rahul Jain
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Attila Pereszlényi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Penghui Yao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Penghui Yao.

Additional information

A preliminary version of this article has appeared in the Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jain, R., Pereszlényi, A. & Yao, P. A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity. Algorithmica 76, 720–748 (2016). https://doi.org/10.1007/s00453-015-0100-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-015-0100-0

Keywords

Mathematics Subject Classification

Search

Navigation