Document Open Access Logo

Communication Memento: Memoryless Communication Complexity

Authors Srinivasan Arunachalam, Supartha Podder

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.61.pdf
  • Filesize: 0.55 MB
  • 20 pages

Document Identifiers

Author Details

Srinivasan Arunachalam
  • IBM T. J. Watson Research Center, Yorktown Heights, NY, USA
Supartha Podder
  • University of Ottawa, Canada

Funding

  • Arunachalam, Srinivasan: Supported in part by the Army Research Laboratory and the Army Research Office under grant number W1975117.

Acknowledgements

We thank Florian Speelman for the proof of the first inequality of Theorem 21 and letting us include it in our paper. We would like to thank Mika Göös, Robert Robere, Dave Touchette and Henry Yuen for helpful pointers. SP also thanks Anne Broadbent and Alexander Kerzner for discussions during the early phase of this project as a part of discussing gardenhose model. We also thank anonymous reviewers for their helpful comments and positive feedback. Part of this work was done when SA was visiting University of Ottawa (hosted by Anne Broadbent) and University of Toronto (hosted by Henry Yuen) and thank them for their hospitality.

Cite AsGet BibTex

Srinivasan Arunachalam and Supartha Podder. Communication Memento: Memoryless Communication Complexity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.61

Abstract

We study the communication complexity of computing functions F: {0,1}ⁿ × {0,1}ⁿ → {0,1} in the memoryless communication model. Here, Alice is given x ∈ {0,1}ⁿ, Bob is given y ∈ {0,1}ⁿ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x (in particular, her reply is independent of the information from the previous rounds); the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that some of these different variants of our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space-bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study all these space-bounded communication complexity models. We establish the following main results: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose model of computation; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c > 1 for which the memoryless communication complexity is at least c log n? Note that c ≥ 2+ε would imply a Ω(n^{2+ε}) lower bound for general formula size, improving upon the best lower bound by [Nečiporuk, 1966].

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
Keywords
  • Communication complexity
  • space complexity
  • branching programs
  • garden-hose model
  • quantum computing

Metrics

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

Related Versions

References

  1. N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. Journal on Computer Systems and Science, 58(1):137-147, 1999. Google Scholar
  2. S. Arunachalam and S. Podder. Communication memento: Memoryless communication complexity. arXiv, 2000. URL: http://arxiv.org/abs/2005.04068.
  3. L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 337-347. IEEE, 1986. Google Scholar
  4. Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis. Exponential separation of quantum and classical one-way communication complexity. SIAM Journal on Computing, 38(1):366-384, 2008. Earlier in STOC'04. Google Scholar
  5. Ziv Bar-Yossef, Thathachar S Jayram, Ravi Kumar, and D Sivakumar. Information theory methods in communication complexity. In Proceedings 17th IEEE Annual Conference on Computational Complexity, pages 93-102. IEEE, 2002. Google Scholar
  6. Ziv Bar-Yossef, Thathachar S Jayram, Ravi 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. Google Scholar
  7. E. Blais, J. Brody, and K. Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21(2):311-358, 2012. Google Scholar
  8. M. Braverman and O. Weinstein. A discrepancy lower bound for information complexity. Algorithmica, 76(3):846-864, 2016. Google Scholar
  9. Mark Braverman. Interactive information complexity. SIAM Journal on Computing, 44(6):1698-1739, 2015. Google Scholar
  10. Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. From information to exact communication. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 151-160, 2013. Google Scholar
  11. J. E. Brody, S. Chen, P. A. Papakonstantinou, H. Song, and X. Sun. Space-bounded communication complexity. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 159-172, 2013. Google Scholar
  12. H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001. Google Scholar
  13. H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and computation. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC), pages 63-68, 1998. Google Scholar
  14. H. Buhrman, L. Czekaj, A. Grudka, M. Horodecki, P. Horodecki, M. Markiewicz, F. Speelman, and S. Strelchuk. Quantum communication complexity advantage implies violation of a bell inequality. Proceedings of the National Academy of Sciences, 113(12):3191-3196, 2016. Google Scholar
  15. H. Buhrman, S. Fehr, C. Schaffner, and F. Speelman. The garden-hose model. In Innovations in Theoretical Computer Science, ITCS, pages 145-158, 2013. Google Scholar
  16. Well Y Chiu, Mario Szegedy, Chengu Wang, and Yixin Xu. The garden hose complexity for the equality function. In International Conference on Algorithmic Applications in Management, pages 112-123. Springer, 2014. Google Scholar
  17. Yfke Dulek, Christian Schaffner, and Florian Speelman. Quantum homomorphic encryption for polynomial-sized circuits. In Annual International Cryptology Conference, pages 3-32. Springer, 2016. Google Scholar
  18. S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf. Exponential lower bounds for polytopes in combinatorial optimization. Journal of the ACM, 62(2):17:1-17:23, 2015. Google Scholar
  19. Anat Ganor, Gillat Kol, and Ran Raz. Exponential separation of information and communication for boolean functions. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 557-566, 2015. Google Scholar
  20. D. Gavinsky. Bare quantum simultaneity versus classical interactivity in communication complexity. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.01381.
  21. D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf. Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM Journal on Computing, 38(5):1695-1708, 2008. Previous in FOCS'07. Google Scholar
  22. Mikael Goldmann and Johan Håstad. A simple lower bound for monotone clique using a communication game. Information Processing Letters, 41(4):221-226, 1992. Google Scholar
  23. R. Impagliazzo and R. Williams. Communication complexity with synchronized clocks. In 2010 IEEE 25th Annual Conference on Computational Complexity, pages 259-269. IEEE, 2010. Google Scholar
  24. M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2):255-265, 1990. Google Scholar
  25. H. Klauck and S. Podder. New bounds for the garden-hose model. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS, pages 481-492, 2014. Google Scholar
  26. Hartmut Klauck. Quantum and classical communication-space tradeoffs from rectangle bounds. In International Conference on Foundations of Software Technology and Theoretical Computer Science, pages 384-395. Springer, 2004. Google Scholar
  27. E. Kushilevitz and N. Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  28. T. Lam, P. Tiwari, and M. Tompa. Tradeoffs between communication and space. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 217-226, 1989. Google Scholar
  29. Tak Lam, Prasoon Tiwari, and Martin Tompa. Trade-offs between communication and space. Journal of Computer and System Sciences, 45(3):296-315, 1992. Google Scholar
  30. Klaus-Jörn Lange, Pierre McKenzie, and Alain Tapp. Reversible space equals deterministic space. Journal of Computer and System Sciences, 60(2):354-367, 2000. Google Scholar
  31. T. Lee and A. Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3(4):263-398, 2009. Google Scholar
  32. P. B. Miltersen, N. Nisan, S. Safra, and A. Wigderson. On data structures and asymmetric communication complexity. Journal on Computer Systems and Science, 57(1):37-49, 1998. Google Scholar
  33. Edward I Nechiporuk. A boolean function. Engl. transl. in Sov. Phys. Dokl., 10:591-593, 1966. Google Scholar
  34. M. Pal. Communication complexity and parallel computing. IEEE Concurrency, 7(2):81-83, 1999. Google Scholar
  35. P. A. Papakonstantinou, D. Scheder, and H. Song. Overlays and limited memory communication. In IEEE 29th Conference on Computational Complexity, CCC, pages 298-308, 2014. Google Scholar
  36. R. Paturi and J. Simon. Probabilistic communication complexity. Journal of Computer and System Sciences, 33(1):106-123, 1986. Google Scholar
  37. R. K. Sinha and J. S. Thathachar. Efficient oblivious branching programs for threshold and mod functions. Journal of Computer and System Sciences, 55(3):373-384, 1997. Google Scholar
  38. F. Speelman. Position-based quantum cryptography and the garden-hose game, 2012. Masters Thesis. Google Scholar
  39. F. Speelman. Position-based quantum cryptography and catalytic computation, 2016. PhD Thesis. Google Scholar
  40. A. Tal. The bipartite formula complexity of inner-product is quadratic, 2016. Earlier in STOC'17. Google Scholar
  41. I. Wegener. The complexity of Boolean functions. BG Teubner, 1987. Google Scholar
  42. R. de Wolf. Nondeterministic quantum query and communication complexities. SIAM Journal on Computing, 32(3):681-699, 2003. Google Scholar
  43. A. C. Yao. Quantum circuit complexity. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 352-361. IEEE, 1993. Google Scholar
  44. A. Chi-Chih Yao. Some complexity questions related to distributive computing. In Proceedings of the eleventh annual ACM symposium on 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 Imprint Privacy Contact