License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.4
URN: urn:nbn:de:0030-drops-175077
Go to the corresponding LIPIcs Volume Portal

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

Communication Complexity of Inner Product in Symmetric Normed Spaces

LIPIcs-ITCS-2023-4.pdf (0.8 MB)


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').

BibTeX - Entry

  author =	{Andoni, Alexandr and B{\l}asiok, Jaros{\l}aw and Filtser, Arnold},
  title =	{{Communication Complexity of Inner Product in Symmetric Normed Spaces}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-175077},
  doi =		{10.4230/LIPIcs.ITCS.2023.4},
  annote =	{Keywords: communication complexity, symmetric norms}

Keywords: communication complexity, symmetric norms
Collection: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI