LIPIcs.CCC.2018.9.pdf
- Filesize: 0.55 MB
- 17 pages
Document
Communication Complexity with Small Advantage
Author
-
Part of:
Volume:
33rd Computational Complexity Conference (CCC 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computational Complexity Conference (CCC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-04
Cite As Get BibTex
Thomas Watson. Communication Complexity with Small Advantage. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CCC.2018.9
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 (STOC 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.
Subject Classification
ACM Subject Classification
- Theory of computation → Communication complexity
Keywords
- Communication
- complexity
- small
- advantage
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702-732, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2003.11.006.
- Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. From information to exact communication. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 151-160. ACM, 2013. URL: http://dx.doi.org/10.1145/2488608.2488628.
- Mark Braverman and Ankur Moitra. An information complexity approach to extended formulations. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 161-170. ACM, 2013. URL: http://dx.doi.org/10.1145/2488608.2488629.
- Mark Braverman and Anup Rao. Information equals amortized communication. IEEE Trans. Information Theory, 60(10):6058-6069, 2014. URL: http://dx.doi.org/10.1109/TIT.2014.2347282.
- Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev. Beyond set disjointness: the communication complexity of finding the intersection. In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 106-113. ACM, 2014. URL: http://dx.doi.org/10.1145/2611462.2611501.
- Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev. Certifying equality with limited interaction. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, volume 28 of LIPIcs, pages 545-581. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.545.
- Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of gap-hamming-distance. SIAM J. Comput., 41(5):1299-1317, 2012. URL: http://dx.doi.org/10.1137/120861072.
- Arkadev Chattopadhyay and Sagnik Mukhopadhyay. Tribes is hard in the message passing model. In Ernst W. Mayr and Nicolas Ollinger, editors, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages 224-237. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.224.
- Mika Göös and T. S. Jayram. A composition theorem for conical juntas. In Ran Raz, editor, 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, volume 50 of LIPIcs, pages 5:1-5:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.5.
- Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman. Rectangles are nonnegative juntas. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 257-266. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746596.
- Mika Göös, Toniann Pitassi, and Thomas Watson. The landscape of communication complexity classes. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 86:1-86:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.86.
- Mika Göös and Thomas Watson. Communication complexity of set-disjointness for all probabilities. Theory of Computing, 12(1):1-23, 2016. URL: http://dx.doi.org/10.4086/toc.2016.v012a009.
- Prahladh Harsha and Rahul Jain. A strong direct product theorem for the tribes function via the smooth-rectangle bound. In Anil Seth and Nisheeth K. Vishnoi, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12-14, 2013, Guwahati, India, volume 24 of LIPIcs, pages 141-152. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2013.141.
- Rahul Jain and Hartmut Klauck. The partition bound for classical communication complexity and query complexity. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010, pages 247-258. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/CCC.2010.31.
- Rahul Jain, Hartmut Klauck, and Shengyu Zhang. Depth-independent lower bounds on the communication complexity of read-once boolean formulas. In My T. Thai and Sartaj Sahni, editors, Computing and Combinatorics, 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19-21, 2010. Proceedings, volume 6196 of Lecture Notes in Computer Science, pages 54-59. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14031-0_8.
- T. S. Jayram, Swastik Kopparty, and Prasad Raghavendra. On the communication complexity of read-once ac^0 formulae. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 329-340. IEEE Computer Society, 2009. URL: http://dx.doi.org/10.1109/CCC.2009.39.
- T. S. Jayram, Ravi Kumar, and D. Sivakumar. Two applications of information complexity. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 673-682. ACM, 2003. URL: http://dx.doi.org/10.1145/780542.780640.
- Hartmut Klauck. Rectangle size bounds and threshold covers in communication complexity. In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark, pages 118-134. IEEE Computer Society, 2003. URL: http://dx.doi.org/10.1109/CCC.2003.1214415.
-
Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997.
- Nikos Leonardos and Michael E. Saks. Lower bounds on the randomized communication complexity of read-once functions. Computational Complexity, 19(2):153-181, 2010. URL: http://dx.doi.org/10.1007/s00037-010-0292-2.
- Alexander A. Razborov. On the distributional complexity of disjointness. Theor. Comput. Sci., 106(2):385-390, 1992. URL: http://dx.doi.org/10.1016/0304-3975(92)90260-M.
- Alexander A. Sherstov. The communication complexity of gap hamming distance. Theory of Computing, 8(1):197-208, 2012. URL: http://dx.doi.org/10.4086/toc.2012.v008a008.
- Thomas Vidick. 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. URL: http://dx.doi.org/10.4086/cjtcs.2012.001.