Document Open Access Logo

Certifying Equality With Limited Interaction

Authors Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.545.pdf
  • Filesize: 0.72 MB
  • 37 pages

Document Identifiers

Author Details

Joshua Brody
Amit Chakrabarti
Ranganath Kondapally
David P. Woodruff
Grigory Yaroslavtsev

Cite As Get BibTex

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev. Certifying Equality With Limited Interaction. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 545-581, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.545

Abstract

The EQUALITY problem is usually one’s first encounter with communication complexity and is one of the most fundamental problems in the field. Although its deterministic and randomized communication complexity were settled decades ago, we find several new things to say about the problem by focusing on three subtle aspects. The first is to consider the expected communication cost (at a worst-case input) for a protocol that uses limited interaction—i.e., a bounded number of rounds of communication—and whose error probability is zero or close to it. The second is to treat the false negative error rate separately from the false positive error rate. The third is to consider the information cost of such protocols. We obtain asymptotically optimal rounds-versus-cost tradeoffs for EQUALITY: both expected communication cost and information cost scale as Theta(log log ... log n), with r-1 logs, where r is the number of rounds. These bounds hold even when the false negative rate approaches 1. For the case of zero-error communication cost, we obtain essentially matching bounds, up to a tiny additive constant. We also provide some applications.

Subject Classification

Keywords
  • equality
  • communication complexity
  • information complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Farid Ablayev. Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science, 175(2):139-159, 1996. Google Scholar
  2. Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, and Toniann Pitassi. The hardness of being private. In IEEE Conference on Computational Complexity, pages 192-202, 2012. Google Scholar
  3. Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137-147, 1999. Preliminary version in Proc. 28th Annual ACM Symposium on the Theory of Computing , pages 20-29, 1996. Google Scholar
  4. 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. Google Scholar
  5. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. In Proc. 41st Annual ACM Symposium on the Theory of Computing, pages 67-76, 2010. Google Scholar
  6. Mark Braverman. Interactive information complexity. In Proc. 44th Annual ACM Symposium on the Theory of Computing, pages 505-524, 2012. Google Scholar
  7. Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. From information to exact communication. In Proc. 45th Annual ACM Symposium on the Theory of Computing, 2013. to appear. Google Scholar
  8. Mark Braverman and Ankur Moitra. An information complexity approach to extended formulations. In Proc. 45th Annual ACM Symposium on the Theory of Computing, 2013. to appear. Google Scholar
  9. Mark Braverman and Anup Rao. Information equals amortized communication. In Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science, pages 748-757, 2011. Google Scholar
  10. Joshua Brody, Amit Chakrabarti, and Ranganath Kondapally. Certifying equality with limited interaction. Technical Report TR12-153, ECCC, 2012. Google Scholar
  11. Harry Buhrman, David García-Soriano, Arie Matsliah, and Ronald de Wolf. The non-adaptive query complexity of testing k-parities. arXiv preprint arXiv:1209.3849, 2012. Google Scholar
  12. Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, and Andrew McGregor. Information cost tradeoffs for augmented index and streaming language recognition. In Proc. 51st Annual IEEE Symposium on Foundations of Computer Science, pages 387-396, 2010. Google Scholar
  13. Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In Proc. 18th Annual IEEE Conference on Computational Complexity, pages 107-117, 2003. Google Scholar
  14. Amit Chakrabarti and Ranganath Kondapally. Everywhere-tight information cost tradeoffs for augmented index. In Proc. 15th International Workshop on Randomization and Approximation Techniques in Computer Science, pages 448-459, 2011. Google Scholar
  15. Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew C. Yao. Informational complexity and the direct sum problem for simultaneous message complexity. In Proc. 42nd Annual IEEE Symposium on Foundations of Computer Science, pages 270-278, 2001. Google Scholar
  16. Amit Chakrabarti and Anna Shubina. Nearly private information retrieval. In Proc. 32nd International Symposium on Mathematical Foundations of Computer Science, volume 4708 of Lecture Notes in Computer Science, pages 383-393, 2007. Google Scholar
  17. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, second edition, 2006. Google Scholar
  18. Anirban Dasgupta, Ravi Kumar, and D. Sivakumar. Sparse and lopsided set disjointness via information theory. In 16th International workshop on Randomization, volume 7409, pages 517-528, 2012. Google Scholar
  19. Ronald Fagin, Moni Naor, and Peter Winkler. Comparing information without leaking it. Commun. ACM, 39(5):77-85, 1996. Google Scholar
  20. Tomas Feder, Eyal Kushilevitz, Moni Naor, and Noam Nisan. Amortized communication complexity. SIAM J. Comput., 24(4):736-750, 1995. Preliminary version in Proc. 32nd Annual IEEE Symposium on Foundations of Computer Science , pages 239-248, 1991. Google Scholar
  21. Michael J. Freedman, Kobbi Nissim, and Benny Pinkas. Efficient private matching and set intersection. In EUROCRYPT, pages 1-19, 2004. Google Scholar
  22. Rusins Freivalds. Probabilistic machines can use less running time. In IFIP Congress, pages 839-842, 1977. Google Scholar
  23. Andre Gronemeier. Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness. In Proc. 26th International Symposium on Theoretical Aspects of Computer Science, pages 505-516, 2009. Google Scholar
  24. Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan. The communication complexity of correlation. In Proc. 22nd Annual IEEE Conference on Computational Complexity, pages 10-23, 2007. Google Scholar
  25. Johan Håstad and Avi Wigderson. The randomized communication complexity of set disjointness. Theory of Computing, pages 211-219, 2007. Google Scholar
  26. Rahul Jain. New strong direct product results in communication complexity. Electronic Colloquium on Computational Complexity (ECCC), 18:24, 2011. Google Scholar
  27. Rahul Jain, Attila Pereszlényi, and Penghui Yao. A direct product theorem for the two-party bounded-round public-coin communication complexity. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science, pages 167-176, 2012. Google Scholar
  28. Rahul Jain, Pranab Sen, and Jaikumar Radhakrishnan. Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. CoRR, abs/0807.1267, 2008. Google Scholar
  29. Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM J. Disc. Math., 5(4):547-557, 1992. Google Scholar
  30. Iordanis Kerenidis and Ronald de Wolf. Exponential lower bound for 2-query locally decodable codes. J. Comput. Syst. Sci., 69(3):395-420, 2004. Preliminary version in Proc. 35th Annual ACM Symposium on the Theory of Computing , pages 106-115, 2003. Google Scholar
  31. Hartmut Klauck. On quantum and approximate privacy. In STACS, pages 335-346, 2002. Google Scholar
  32. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, Cambridge, 1997. Google Scholar
  33. Eyal Kushilevitz and Enav Weinreb. The communication complexity of set-disjointness with small sets and 0-1 intersection. In Proc. 50th Annual IEEE Symposium on Foundations of Computer Science, pages 63-72, 2009. Google Scholar
  34. Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. Recognizing well-parenthesized expressions in the streaming model. In Proc. 41st Annual ACM Symposium on the Theory of Computing, pages 261-270, 2010. Google Scholar
  35. Kurt Mehlhorn and Erik M. Schmidt. Las Vegas is better than determinism in VLSI and distributed computing (extended abstract). In Proc. 14th Annual ACM Symposium on the Theory of Computing, pages 330-337, 1982. Google Scholar
  36. Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. J. Comput. Syst. Sci., 57(1):37-49, 1998. Preliminary version in Proc. 27th Annual ACM Symposium on the Theory of Computing , pages 103-111, 1995. Google Scholar
  37. M. Molinaro, D.P. Woodruff, and G. Yaroslavtsev. Beating the direct sum theorem in communication complexity with implications for sketching. In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 2013. Google Scholar
  38. Moni Naor and Benny Pinkas. Oblivious polynomial evaluation. SIAM J. Comput., 35(5):1254-1281, 2006. Google Scholar
  39. Ashwin Nayak. Optimal lower bounds for quantum automata and random access codes. In Proc. 40th Annual IEEE Symposium on Foundations of Computer Science, pages 124-133, 1999. Google Scholar
  40. Mihai Pǎtraşcu. Unifying the landscape of cell-probe lower bounds. SIAM J. Comput., 40(3):827-847, 2011. Google Scholar
  41. Alexander Razborov. On the distributional complexity of disjointness. Theor. Comput. Sci., 106(2):385-390, 1992. Preliminary version in Proc. 17th International Colloquium on Automata, Languages and Programming , pages 249-253, 1990. Google Scholar
  42. Mert Saglam and Gábor Tardos. On the communication complexity of sparse set disjointness and exists-equal problems. In Proc. 54th Annual IEEE Symposium on Foundations of Computer Science, pages 678-687, 2013. Google Scholar
  43. Andrew C. Yao. Probabilistic computations: Towards a unified measure of complexity. In Proc. 18th Annual IEEE Symposium on Foundations of Computer Science, pages 222-227, 1977. Google Scholar
  44. Andrew C. Yao. Some complexity questions related to distributive computing. In Proc. 11th Annual ACM Symposium on the Theory of Computing, pages 209-213, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact