Document Open Access Logo

Communication Complexity of Inner Product in Symmetric Normed Spaces

Authors Alexandr Andoni, Jarosław Błasiok, Arnold Filtser



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.4.pdf
  • Filesize: 0.8 MB
  • 22 pages

Document Identifiers

Author Details

Alexandr Andoni
  • Columbia University, New York, NY, USA
Jarosław Błasiok
  • Columbia University, New York, NY, USA
Arnold Filtser
  • Bar-Ilan University, Ramat-Gan, Israel

Cite AsGet BibTex

Alexandr Andoni, Jarosław Błasiok, and Arnold Filtser. Communication Complexity of Inner Product in Symmetric Normed Spaces. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.4

Abstract

We introduce and study the communication complexity of computing the inner product of two vectors, where the input is restricted w.r.t. a norm N on the space ℝⁿ. Here, Alice and Bob hold two vectors v,u such that ‖v‖_N ≤ 1 and ‖u‖_{N^*} ≤ 1, where N^* is the dual norm. The goal is to compute their inner product ⟨v,u⟩ up to an ε additive term. The problem is denoted by IP_N, and generalizes important previously studied problems, such as: (1) Computing the expectation 𝔼_{x∼𝒟}[f(x)] when Alice holds 𝒟 and Bob holds f is equivalent to IP_{𝓁₁}. (2) Computing v^TAv where Alice has a symmetric matrix with bounded operator norm (denoted S_∞) and Bob has a vector v where ‖v‖₂ = 1. This problem is complete for quantum communication complexity and is equivalent to IP_{S_∞}. We systematically study IP_N, showing the following results, near tight in most cases: 1) For any symmetric norm N, given ‖v‖_N ≤ 1 and ‖u‖_{N^*} ≤ 1 there is a randomized protocol using 𝒪̃(ε^{-6} log n) bits of communication that returns a value in ⟨u,v⟩±ε with probability 2/3 - we will denote this by ℛ_{ε,1/3}(IP_N) ≤ 𝒪̃(ε^{-6} log n). In a special case where N = 𝓁_p and N^* = 𝓁_q for p^{-1} + q^{-1} = 1, we obtain an improved bound ℛ_{ε,1/3}(IP_{𝓁_p}) ≤ 𝒪(ε^{-2} log n), nearly matching the lower bound ℛ_{ε, 1/3}(IP_{𝓁_p}) ≥ Ω(min(n, ε^{-2})). 2) One way communication complexity ℛ^{→}_{ε,δ}(IP_{𝓁_p}) ≤ 𝒪(ε^{-max(2,p)}⋅ log n/ε), and a nearly matching lower bound ℛ^{→}_{ε, 1/3}(IP_{𝓁_p}) ≥ Ω(ε^{-max(2,p)}) for ε^{-max(2,p)} ≪ n. 3) One way communication complexity ℛ^{→}_{ε,δ}(N) for a symmetric norm N is governed by the distortion of the embedding 𝓁_∞^k into N. Specifically, while a small distortion embedding easily implies a lower bound Ω(k), we show that, conversely, non-existence of such an embedding implies protocol with communication k^𝒪(log log k) log² n. 4) For arbitrary origin symmetric convex polytope P, we show ℛ_{ε,1/3}(IP_{N}) ≤ 𝒪(ε^{-2} log xc(P)), where N is the unique norm for which P is a unit ball, and xc(P) is the extension complexity of P (i.e. the smallest number of inequalities describing some polytope P' s.t. P is projection of P').

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
Keywords
  • communication complexity
  • symmetric norms

Metrics

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

References

  1. Scott Aaronson. Quantum Computing since Democritus. Cambridge University Press, 2013. URL: http://www.cambridge.org/de/academic/subjects/physics/quantum-physics-quantum-information-and-quantum-computation/quantum-computing-democritus?format=PB.
  2. Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten. Approximate near neighbors for general symmetric norms. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 902-913, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3055399.3055418.
  3. Joshua Brody and Amit Chakrabarti. A multi-round communication lower bound for gap hamming and some consequences. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 358-368. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/CCC.2009.31.
  4. Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, and Ronald de Wolf. Better gap-hamming lower bounds via better round elimination. In Maria J. Serna, Ronen Shaltiel, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, volume 6302 of Lecture Notes in Computer Science, pages 476-489. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15369-3_36.
  5. Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, and Madhu Sudan. Communication with imperfectly shared randomness. IEEE Transactions on Information Theory, 63(10):6799-6818, 2017. URL: https://doi.org/10.1109/TIT.2017.2734103.
  6. Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of gap-hamming-distance. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, pages 51-60, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/1993636.1993644.
  7. M. Conforti, G. Cornuéjols, and G. Zambelli. Integer Programming. Graduate Texts in Mathematics. Springer International Publishing, 2014. URL: https://books.google.com/books?id=antqBQAAQBAJ.
  8. Yuri Faenza, Samuel Fiorini, Roland Grappe, and Hans Raj Tiwary. Extended formulations, nonnegative factorizations, and randomized communication protocols. In A. Ridha Mahjoub, Vangelis Markakis, Ioannis Milis, and Vangelis Th. Paschos, editors, Combinatorial Optimization, pages 129-140, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  9. Mika Göös, Rahul Jain, and Thomas Watson. Extension complexity of independent set polytopes. SIAM Journal on Computing, 47(1):241-269, 2018. URL: https://doi.org/10.1137/16M109884X.
  10. Piotr Indyk and David P. Woodruff. Tight lower bounds for the distinct elements problem. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 283-288. IEEE Computer Society, 2003. URL: https://doi.org/10.1109/SFCS.2003.1238202.
  11. T. S. Jayram, Ravi Kumar, and D. Sivakumar. The one-way communication complexity of hamming distance. Theory Comput., 4(1):129-135, 2008. URL: https://doi.org/10.4086/toc.2008.v004a006.
  12. W.B. Johnson and J. Lindenstrauss. Handbook of the Geometry of Banach Spaces. Number v. 1-2 in Handbook of the Geometry of Banach Spaces. Elsevier, 2001. URL: https://books.google.co.vi/books?id=sl3qiUdrXU8C.
  13. Bo'az Klartag and Oded Regev. Quantum one-way communication can be exponentially stronger than classical communication. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 31-40. ACM, 2011. URL: https://doi.org/10.1145/1993636.1993642.
  14. Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff. Approximate nonnegative rank is equivalent to the smooth rectangle bound. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming, pages 701-712, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. Google Scholar
  15. Ilan Kremer. Quantum communication. Citeseer, 1995. Google Scholar
  16. Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC '95, pages 596-605, New York, NY, USA, 1995. Association for Computing Machinery. URL: https://doi.org/10.1145/225058.225277.
  17. Ilan Newman. Private vs. common random bits in communication complexity. Inf. Process. Lett., 39(2):67-71, July 1991. URL: https://doi.org/10.1016/0020-0190(91)90157-D.
  18. Ran Raz. Exponential separation of quantum and classical communication complexity. In Jeffrey Scott Vitter, Lawrence L. Larmore, and Frank Thomson Leighton, editors, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA, pages 358-367. ACM, 1999. URL: https://doi.org/10.1145/301250.301343.
  19. Tim Roughgarden. Communication complexity (for algorithm designers). Foundations and Trends® in Theoretical Computer Science, 11(3–4):217-404, 2016. URL: https://doi.org/10.1561/0400000076.
  20. Alexander A. Sherstov. The communication complexity of gap hamming distance. Theory of Computing, 8(8):197-208, 2012. URL: https://doi.org/10.4086/toc.2012.v008a008.
  21. Santosh S Vempala. The random projection method, volume 65. American Mathematical Soc., 2005. Google Scholar
  22. 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. Electron. Colloquium Comput. Complex., 18:51, 2011. Google Scholar
  23. David P. Woodruff. Optimal space lower bounds for all frequency moments. In J. Ian Munro, editor, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004, pages 167-175. SIAM, 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982817.
  24. David P. Woodruff. The average-case complexity of counting distinct elements. In Ronald Fagin, editor, Database Theory - ICDT 2009, 12th International Conference, St. Petersburg, Russia, March 23-25, 2009, Proceedings, volume 361 of ACM International Conference Proceeding Series, pages 284-295. ACM, 2009. URL: https://doi.org/10.1145/1514894.1514928.
  25. Mihalis Yannakakis. Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences, 43(3):441-466, 1991. URL: https://doi.org/10.1016/0022-0000(91)90024-Y.
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