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
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17507/
Andoni, Alexandr ;
Błasiok, Jarosław ;
Filtser, Arnold
Communication Complexity of Inner Product in Symmetric Normed Spaces
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').
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: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 = {https://drops.dagstuhl.de/opus/volltexte/2023/17507},
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 |
