Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Communication Complexity with Small Advantage

  • Published:
computational complexity Aims and scope Submit manuscript

A Correction to this article was published on 30 May 2020

This article has been updated

Abstract

We study problems in randomized communication complexity when the protocol is only required to attain some small advantage over purely random guessing, i.e., it produces the correct output with probability at least \(\epsilon\) greater than one over the codomain size of the function. Previously, Braverman and Moitra (in: Proceedings of the 45th symposium on theory of computing (STOC), ACM, pp 161–170, 2013) showed that the set-intersection function requires \(\Theta(\epsilon{n})\) communication to achieve advantage \(\epsilon\). Building on this, we prove the same bound for several variants of set-intersection: (1) the classic “tribes” function obtained by composing with And (provided \(1/\epsilon\) is at most the width of the And), and (2) the variant where the sets are uniquely intersecting and the goal is to determine partial information about (say, certain bits of the index of) the intersecting coordinate.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Change history

  • 30 May 2020

    Authors would like to correct the incorrect author references in the online published article.

References

  • Ambainis, Andris, Schulman, Leonard, Ta-Shma, Amnon, Vazirani, Umesh, Wigderson, Avi: The Quantum Communication Complexity of Sampling. SIAM Journal on Computing 32(6), 1570–1585 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  • Ziv Bar-Yossef, T.S., Jayram, Ravi Kumar, Sivakumar, D.: An Information Statistics Approach to Data Stream and Communication Complexity. Journal of Computer and System Sciences 68(4), 702–732 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  • Braverman, Mark: Interactive Information Complexity. SIAM Journal on Computing 44(6), 1698–1739 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  • Mark Braverman, Ankit Garg, Denis Pankratov & Omri Weinstein (2013). From Information to Exact Communication. In Proceedings of the 45th Symposium on Theory of Computing (STOC), 151–160

  • Mark Braverman & Ankur Moitra (2013). An Information Complexity Approach to Extended Formulations. In Proceedings of the 45th Symposium on Theory of Computing (STOC), 161–170. ACM

  • Mark Braverman & Anup Rao: Information Equals Amortized Communication. IEEE Transactions on Information Theory 60(10), 6058–6069 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  • Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David Woodruff & Grigory Yaroslavtsev (2014). Beyond Set Disjointness: The Communication Complexity of Finding the Intersection. In Proceedings of the 33rd Symposium on Principles of Distributed Computing (PODC), 106–113. ACM

  • Brody, Joshua, Chakrabarti, Amit, Kondapally, Ranganath, Woodruff, David, Yaroslavtsev, Grigory: Certifying Equality With Limited Interaction. Algorithmica 76(3), 796–845 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  • Amit Chakrabarti & Oded Regev: An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. SIAM Journal on Computing 41(5), 1299–1317 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  • Arkadev Chattopadhyay & Sagnik Mukhopadhyay (2015). Tribes Is Hard in the Message Passing Model. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS), 224–237. Schloss Dagstuhl

  • Benny Chor & Oded Goldreich: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity. SIAM Journal on Computing 17(2), 230–261 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  • Thomas Cover & Joy Thomas (2006). Elements of Information Theory. Wiley.

  • Mika Göös & T. S. Jayram (2016). A Composition Theorem for Conical Juntas. In Proceedings of the 31st Computational Complexity Conference (CCC), 5:1–5:16. Schloss Dagstuhl

  • Mika Göös, T. S. Jayram, Toniann Pitassi & Thomas Watson (2018a). Randomized Communication vs. Partition Number. ACM Transactions on Computation Theory10(1), 4:1–4:20

  • Göös, Mika, Lovett, Shachar, Meka, Raghu, Watson, Thomas, Zuckerman, David: Rectangles Are Nonnegative Juntas. SIAM Journal on Computing 45(5), 1835–1869 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  • Mika Göös, Toniann Pitassi & Thomas Watson (2017). Query-to-Communication Lifting for BPP. In Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS), 132–143. IEEE

  • Göös, Mika, Pitassi, Toniann, Watson, Thomas: The Landscape of Communication Complexity Classes. Computational Complexity 27(2), 245–304 (2018b)

    Article  MathSciNet  MATH  Google Scholar 

  • Mika Göös & Thomas Watson: Communication Complexity of Set-Disjointness for All Probabilities. Theory of Computing 12(9), 1–23 (2016)

    MathSciNet  MATH  Google Scholar 

  • Prahladh Harsha & Rahul Jain (2013). A Strong Direct Product Theorem for the Tribes Function via the Smooth-Rectangle Bound. In Proceedings of the 33rd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 141–152. Schloss Dagstuhl

  • Rahul Jain & Hartmut Klauck (2010). The Partition Bound for Classical Communication Complexity and Query Complexity. In Proceedings of the 25th Conference on Computational Complexity (CCC), 247–258. IEEE

  • Rahul Jain, Hartmut Klauck & Shengyu Zhang (2010). Depth-Independent Lower Bounds on the Communication Complexity of Read-Once Boolean Formulas. In Proceedings of the 16th International Computing and Combinatorics Conference (COCOON), 54–59. Springer

  • Jain, Rahul, Shi, Yaoyun, Wei, Zhaohui, Zhang, Shengyu: Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States. IEEE Transactions on Information Theory 59(8), 5171–5178 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  • T.S. Jayram, Swastik Kopparty & Prasad Raghavendra (2009). On the Communication Complexity of Read-Once \({\rm AC}^{0}\) Formulae. In Proceedings of the 24th Conference on Computational Complexity (CCC), 329–340. IEEE

  • T.S. Jayram, Ravi Kumar & D. Sivakumar (2003). Two Applications of Information Complexity. In Proceedings of the 35th Symposium on Theory of Computing (STOC), 673–682. ACM

  • Hartmut Klauck (2003). Rectangle Size Bounds and Threshold Covers in Communication Complexity. In Proceedings of the 18th Conference on Computational Complexity (CCC), 118–134. IEEE

  • Nikos Leonardos & Michael Saks: Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. Computational Complexity 19(2), 153–181 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  • Razborov, Alexander: On the Distributional Complexity of Disjointness. Theoretical Computer Science 106(2), 385–390 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  • Alexander Razborov & Alexander Sherstov: The Sign-Rank of \(\rm AC^0\). SIAM Journal on Computing 39(5), 1833–1855 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  • Sherstov, Alexander: The Communication Complexity of Gap Hamming Distance. Theory of Computing 8(1), 197–208 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  • Vidick, Thomas: A Concentration Inequality for the Overlap of a Vector on a Large Set, with Application to the Communication Complexity of the Gap-Hamming-Distance Problem. Chicago Journal of Theoretical Computer Science 2012(1), 1–12 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  • Watson, Thomas: Time Hierarchies for Sampling Distributions. SIAM Journal on Computing 43(5), 1709–1727 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  • Thomas Watson (2016). Nonnegative Rank vs. Binary Rank. Chicago Journal of Theoretical Computer Science2016(2), 1–13

  • Thomas Watson (2018). Communication Complexity with Small Advantage. In Proceedings of the 33rd Computational Complexity Conference (CCC), 9:1–9:17. Schloss Dagstuhl

Download references

Acknowledgements

A preliminary version of this paper was published asWatson (2018). We thank anonymous reviewers for their comments.

Author information

Authors and Affiliations

  1. University of Memphis, Memphis, TN, USA

    Thomas Watson

Authors
  1. Thomas Watson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thomas Watson.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The original version of this article was revised: Error in author references were corrected.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Watson, T. Communication Complexity with Small Advantage. comput. complex. 29, 2 (2020). https://doi.org/10.1007/s00037-020-00192-w

Download citation

  • Received:

  • Published:

  • DOI: https://doi.org/10.1007/s00037-020-00192-w

Keywords

Subject classification

Search

Navigation