# Estimating inner product over $[r]^d$

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$$ 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)$$?

• What is $[r]$? Do you mean, e.g., $[0,r]$? – Neal Young Apr 10 '19 at 20:54
• I should have clarified, it means integers from 0 to r. – Dawei Huang Apr 10 '19 at 20:55
• 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$? – Neal Young Apr 10 '19 at 20:57
• 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$. – Dawei Huang Apr 10 '19 at 21:06
• 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$. – 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$$.
• 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$. – Dawei Huang Apr 11 '19 at 18:04