research-article

Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract

Authors:

Hartmut Klauck,

Ashwin NayakAuthors Info & Claims

STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

Pages 599 - 608

https://doi.org/10.1145/1374376.1374462

Published: 17 May 2008 Publication History

Abstract

A basic question in complexity theory is whether the computational resources required for solving k independent instances of the same problem scale as k times the resources required for one instance. We investigate this question in various models of classical communication complexity. We introduce a new measure, the subdistribution bound , which is a relaxation of the well-studied rectangle or corruption bound in communication complexity. We nonetheless show that for the communication complexity of Boolean functions with constant error, the subdistribution bound is the same as the latter measure, up to a constant factor. We prove that the one-way version of this bound tightly captures the one-way public-coin randomized communication complexity of any relation, and the two-way version bounds the two-way public-coin randomized communication complexity from below. More importantly, we show that the bound satisfies the strong direct product property under product distributions for both one- and two-way protocols, and the weak direct product property under arbitrary distributions for two-way protocols. These results subsume and strengthen, in a unified manner, several recent results on the direct product question. The simplicity and broad applicability of our technique is perhaps an indication of its potential to solve yet more challenging questions regarding the direct product problem.

References

[1]

S. Aaronson. Limitations of quantum advice and one-way communication. In Proceedings of the 19th Annual IEEE Conference on Computational Complexity, pages 320--332, 2004.

Digital Library

[2]

A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani. Dense quantum coding and a lower bound for 1-way quantum automata. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pages 376--383. ACM Press, 1999.

Digital Library

[3]

A. Ambainis, R. Spalek, and R. de Wolf. A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pages 618--633. ACM Press, May21--23 2006.

Digital Library

[4]

L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, pages 337--347, 1986.

Digital Library

[5]

Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702--732, 2004. Special issue on FOCS 2002.

Digital Library

[6]

P. Beame, T. Pitassi, N. Segerlind, and A. Wigderson. A direct sum theorem for corruption and a lower bound for the multiparty communication complexity of Set Disjointness. Computational Complexity, 2007.

Digital Library

[7]

A. Ben-Aroya, O. Regev, and R. de Wolf. A hypercontractive inequality for matrix-valued functions with applications to quantum computing. Technical Report arXiv:0705.3806v1, ArXiv.org Preprint Archive, http://arxiv.org/, May 2007.

[8]

A. Chakrabarti and O. Regev. An optimal randomised cell probe lower bound for approximate nearest neighbour searching. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pages 473--482, 2004.

Digital Library

[9]

R. Cleve, W. Slofstra, F. Unger, and S. Upadhyay. Perfect parallel repetition theorem for quantum XOR proof systems. In Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, 2007.

Digital Library

[10]

T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley Series in Telecommunications. John Wiley & Sons, New York, NY, USA, 1991.

Digital Library

[11]

R. de Wolf. Random access codes, direct product theorems, and multiparty communication complexity. Unpublished manuscript, incorporated into \citeBen-AroyaRdW07, 2005.

[12]

D. Gavinsky. On the role of shared entanglement. Quantum Information and Computation, Vol.8 No.1&2:0082--0095, 2008.

Digital Library

[13]

O. Goldreich, N. Nisan, and A. Wigderson. On Yao's XOR-lemma. Technical Report TR95-050, Electronic Colloquium on Computational Complexity, http://http://eccc.hpi-web.de/eccc/, 1995. Revision 1, January 1999.

[14]

R. Impagliazzo, R. Raz, and A. Wigderson. A direct product theorem. In Proceedings of the Ninth Annual IEEE Structure in Complexity Theory Conference, pages 88--96, 1994.

[15]

R. Jain, J. Radhakrishnan, and P. Sen. Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 429--438, 2002.

Digital Library

[16]

R. Jain, J. Radhakrishnan, and P. Sen. On divergence, relative entropy and the substate property. Technical Report quant-ph/0506210, ArXiv.org Preprint Archive, http://www.arxiv.org/abs/quant-ph/, June 2005.

[17]

M. Karchmer, R. Raz, and A. Wigderson. Super-logarithmic depth lower bounds via direct sum in communication complexity. Computational Complexity, 5:191--204, 1995.

[18]

H. Klauck. Quantum and classical communication-space tradeoffs from rectangle bounds. In Proceedings of the 24th Annual IARCS International Conference on Foundations of Software Technology and Theoretical Computer Science, volume 3328 of Lecture notes in Computer Science, pages 384--395. Springer, Berlin/Heidelberg, 2004.

Digital Library

[19]

H. Klauck, R. Spalek, and R. de Wolf. Quantum and classical strong direct product theorems and optimal time-space tradeoffs. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pages 12--21, 2004.

Digital Library

[20]

I. Kremer, N. Nisan, and D. Ron. On randomized one-round communication complexity. Computational Complexity, 8(1):21--49, 1999. Corrected version available at http://www.eng.tau.ac.il/ danar/Public-pdf/KNR-fix.pdf.

Digital Library

[21]

E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, Cambridge, UK, 1997.

Digital Library

[22]

I. Parnafes, R. Raz, and A. Wigderson. Direct product results and the GCD problem, in old and new communication models. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 363--372, 1997.

Digital Library

[23]

M. Patrascu and M. Thorup. Higher lower bounds for near-neighbor and further rich problems. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 646--654. IEEE Computer Society Press, Los Alamitos, CA, USA, 2006.

Digital Library

[24]

R. Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763--803, 1998.

Digital Library

[25]

R. Shaltiel. Towards proving strong direct product theorems. Computational Complexity, 12(1--2):1--22, 2003.

Digital Library

[26]

A. A. Sherstov. Communication complexity under product and nonproduct distributions. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008.\endthebibliography

Digital Library

Cited By

Boddu NJain RLin H(2023)On relating one-way classical and quantum communication complexitiesQuantum10.22331/q-2023-05-22-10107(1010)Online publication date: 22-May-2023
https://doi.org/10.22331/q-2023-05-22-1010
Jain RKundu S(2021)A direct product theorem for one-way quantum communicationProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.27Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.27
Jain R(2021)Chain-Rules for Channel Capacity2021 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT45174.2021.9518181(262-267)Online publication date: 12-Jul-2021
https://doi.org/10.1109/ISIT45174.2021.9518181
Show More Cited By

Index Terms

Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract

Recommendations

New Strong Direct Product Results in Communication Complexity

We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let f ⊆ X × Y × Z be a relation and ϵ > 0 be a constant. Let R^1,pub_ϵ(f) represent the communication ...
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness

We prove that two-party randomized communication complexity satisfies a strong direct product property, so long as the communication lower bound is proved by a "corruption" or "one-sided discrepancy" method over a rectangular distribution. We use this ...
A Direct Product Theorem for the Two-Party Bounded-Round Public-Coin Communication Complexity
FOCS '12: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

May 2008

712 pages

ISBN:9781605580470

DOI:10.1145/1374376

General Chair:
Richard Ladner
University of Washington
,
Program Chair:
Cynthia Dwork
Microsoft Research, Silicon Valley

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 May 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '08

Sponsor:

STOC '08: Symposium on Theory of Computing

May 17 - 20, 2008

British Columbia, Victoria, Canada

Acceptance Rates

STOC '08 Paper Acceptance Rate 80 of 325 submissions, 25%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
305
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Boddu NJain RLin H(2023)On relating one-way classical and quantum communication complexitiesQuantum10.22331/q-2023-05-22-10107(1010)Online publication date: 22-May-2023
https://doi.org/10.22331/q-2023-05-22-1010
Jain RKundu S(2021)A direct product theorem for one-way quantum communicationProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.27Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.27
Jain R(2021)Chain-Rules for Channel Capacity2021 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT45174.2021.9518181(262-267)Online publication date: 12-Jul-2021
https://doi.org/10.1109/ISIT45174.2021.9518181
Göös MWatson T(2020)A Lower Bound for Sampling Disjoint SetsACM Transactions on Computation Theory10.1145/340485812:3(1-13)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.1145/3404858
Chattopadhyay AKoucký MLoff BMukhopadhyay S(2019)Simulation Theorems via Pseudo-random Propertiescomputational complexity10.1007/s00037-019-00190-7Online publication date: 18-Jul-2019
https://doi.org/10.1007/s00037-019-00190-7
Jain RPereszlényi AYao P(2016)A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication ComplexityAlgorithmica10.1007/s00453-015-0100-076:3(720-748)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1007/s00453-015-0100-0
Jain R(2015)New Strong Direct Product Results in Communication ComplexityJournal of the ACM10.1145/269943262:3(1-27)Online publication date: 30-Jun-2015
https://dl.acm.org/doi/10.1145/2699432
Sherstov A(2014)Communication Lower Bounds Using Directional DerivativesJournal of the ACM10.1145/262933461:6(1-71)Online publication date: 17-Dec-2014
https://dl.acm.org/doi/10.1145/2629334
Sherstov A(2014)Communication Complexity Theory: Thirty-Five Years of Set DisjointnessMathematical Foundations of Computer Science 201410.1007/978-3-662-44522-8_3(24-43)Online publication date: 2014
https://doi.org/10.1007/978-3-662-44522-8_3
Sherstov ABoneh DRoughgarden TFeigenbaum J(2013)Communication lower bounds using directional derivativesProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488725(921-930)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488725
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents