Alice has a vector $x \in [r]^d$ and Bob has $y \in [r]^d$, where $[r] \stackrel{\rm def}{=} \{0,1,\dots,r\}$. Alice send a message $M(x)$ to Bob and Bob wants to estimate the inner product $\left<x,y\right>$ with multiplicative error $\epsilon$ with probability $1 - \delta$.

My question is. Is there any known lower bound on $|M(x)|$? My intuition tells me that Alice pretty much has to estimate each coordinate of $x$ up to $\epsilon$ precision since Bob can have an input that zeros out all but one of the entry. Does that give you something like $\Omega(d \log 1/\epsilon)$?

  • $\begingroup$ What is $[r]$? Do you mean, e.g., $[0,r]$? $\endgroup$ – Neal Young Apr 10 '19 at 20:54
  • $\begingroup$ I should have clarified, it means integers from 0 to r. $\endgroup$ – Dawei Huang Apr 10 '19 at 20:55
  • $\begingroup$ Then surely your bound should depend on $r$? E.g., even with $\epsilon=d=1$ and $\delta=1/2$, Bob needs to know something about the magnitude of $x_1$? $\endgroup$ – Neal Young Apr 10 '19 at 20:57
  • $\begingroup$ Then maybe it should be something like $d(\log \log r + \log 1/\epsilon)$? This is the number of bits you need to if we round $x_i$ to the nearest exponent of $1+\epsilon$. $\endgroup$ – Dawei Huang Apr 10 '19 at 21:06
  • $\begingroup$ I agree that Alice can do it deterministically with that many bits, and can't do better deterministically. If the inner product is at least some $T$, it would be enough for Alice to choose some $k=O(\log(1/\delta) d r^2/(T \epsilon^2))$ indices $i\in[d]$ at random, and just send the approximate $x_i$ for each of those. (Bob would compute the corresponding random sample.) This would be better when $\log(1/\delta) r^2 \ll \epsilon^2 T$. $\endgroup$ – Neal Young Apr 10 '19 at 21:39

In the indexing problem Alice has a vector $x \in \{0,1\}^d$ and Bob has a number $i$, and Bob wants to learn $x_i$. The randomized one-way communication complexity of this problem is $\Omega(d)$ (see Section 3 of this paper), and it can be solved by approximating $x_i = \langle x, e_i\rangle$ up to any multiplicative factor where $e_i$ is the vector with $1$ in the $i$-th coordinate and $0$'s everywhere else. So your problem has $\Theta(d)$ randomized one-way communication complexity for $r=1$.

  • $\begingroup$ Thanks! I think this paper also contain a bound $\Omega(n/(T\epsilon^2))$ that also show dependence on $\epsilon$. I wonder whether it makes sense or not to ask how the bound generalizes to general $r$. $\endgroup$ – Dawei Huang Apr 11 '19 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.