Communication Complexity of Inner Product in Symmetric Normed Spaces

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

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 ${\mathbb{R}}^n$. Here…