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, nonexistence 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
@InProceedings{andoni_et_al:LIPIcs.ITCS.2023.4,
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:14:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17507},
URN = {urn:nbn:de:0030drops175077},
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 