论文标题
内部产品在对称规范空间中的沟通复杂性
Communication Complexity of Inner Product in Symmetric Normed Spaces
论文作者
论文摘要
我们介绍和研究计算两个向量的内部产品的通信复杂性，其中输入受到限制。空间$ \ mathbb {r}^n $上的标准$ n $。在这里，爱丽丝和鲍勃持有两个向量$ v，u $，以便$ \ | v \ | _n \ le 1 $和$ \ | | _ | _ {n^*} \ le 1 $，其中$ n^*$是双重标准。他们想计算其内部产品$ \ langle v，u \ rangle $ to $ \ varepsilon $添加术语。问题由$ \ mathrm {ip} _n $表示。 我们系统地研究$ \ mathrm {ip} _n $，显示以下结果： - 对于任何对称的规范$ n $，给定$ \ | | | | _n \ le 1 $和$ \ | | U \ | | _ {n^*} \ le 1 $，有一个随机协议，用于$ \ mathrm {ip} _n $使用$ \ tilde {\ tilde {我们将用$ \ Mathcal {r} _ {\ Varepsilon，1/3}（\ Mathrm {ip} _ {n}）\ leq \ tilde {\ tilde {\ Mathcal {o}}（\ varepsilon^{ - 6} { - 6} \ log n）$。 - 通信复杂性$ \ oferrightarrow {\ mathcal {r}}（\ m缩$ \ oferrightArrow {\ Mathcal {r}}（\ Mathrm {ip} _ {\ ell_p}）\ geqω（\ varepsilon^{ - \ max（2，p）}）$ for $ \ varepsilon^varepsilon^{ - \ max（2，p）（2，p），2，p）} $。 - 一种方式通信复杂性$ \ oferrightArrow {\ Mathcal {r}}（n）$用于对称的norm $ n $，由嵌入$ \ ell_ \ ell_ \ infty^k $控制到$ n $。具体而言，虽然嵌入的小失真很容易意味着下限的$ω（k）$，但我们表明，这种嵌入的嵌入不存在意味着与通信$ k^{\ Mathcal {o}（\ log \ log \ log \ log k）} \ log log log^2 n $。 - 对于任意起源对称凸$ P $，我们显示$ \ Mathcal {r}（\ Mathrm {ip} _ {n}）\ le \ le \ natrcal {o}（\ varepsilon^{ - 2} { - 2} \ log log \ log \ mathrm {xc nis $ n $ n $ n $ s $ n $ n $ n $ n $ n $ nord o n $ n $ wher $ \ mathrm {xc}（p）$是$ p $的扩展复杂度。
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, Alice and Bob hold two vectors $v,u$ such that $\|v\|_N\le 1$ and $\|u\|_{N^*}\le 1$, where $N^*$ is the dual norm. They want to compute their inner product $\langle v,u \rangle$ up to an $\varepsilon$ additive term. The problem is denoted by $\mathrm{IP}_N$. We systematically study $\mathrm{IP}_N$, showing the following results: - For any symmetric norm $N$, given $\|v\|_N\le 1$ and $\|u\|_{N^*}\le 1$ there is a randomized protocol for $\mathrm{IP}_N$ using $\tilde{\mathcal{O}}(\varepsilon^{-6} \log n)$ bits -- we will denote this by $\mathcal{R}_{\varepsilon,1/3}(\mathrm{IP}_{N}) \leq \tilde{\mathcal{O}}(\varepsilon^{-6} \log n)$. - One way communication complexity $\overrightarrow{\mathcal{R}}(\mathrm{IP}_{\ell_p})\leq\mathcal{O}(\varepsilon^{-\max(2,p)}\cdot \log\frac n\varepsilon)$, and a nearly matching lower bound $\overrightarrow{\mathcal{R}}(\mathrm{IP}_{\ell_p}) \geq Ω(\varepsilon^{-\max(2,p)})$ for $\varepsilon^{-\max(2,p)} \ll n$. - One way communication complexity $\overrightarrow{\mathcal{R}}(N)$ for a symmetric norm $N$ is governed by embeddings $\ell_\infty^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^{\mathcal{O}(\log \log k)} \log^2 n$. - For arbitrary origin symmetric convex polytope $P$, we show $\mathcal{R}(\mathrm{IP}_{N}) \le\mathcal{O}(\varepsilon^{-2} \log \mathrm{xc}(P))$, where $N$ is the unique norm for which $P$ is a unit ball, and $\mathrm{xc}(P)$ is the extension complexity of $P$.
