3
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ What is $[r]$? Do you mean, e.g., $[0,r]$? $\endgroup$
    – Neal Young
    Apr 10, 2019 at 20:54
  • $\begingroup$ I should have clarified, it means integers from 0 to r. $\endgroup$
    – Dawei Huang
    Apr 10, 2019 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, 2019 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, 2019 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, 2019 at 21:39

1 Answer 1

Reset to default
3
$\begingroup$

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$.

Improve this answer
$\endgroup$
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, 2019 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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