<p>In the indexing problem Alice has a vector <span class="math-container">$x \in \{0,1\}^d$</span> and Bob has a number <span class="math-container">$i$</span>, and Bob wants to learn <span class="math-container">$x_i$</span>. The randomized one-way communication complexity of this problem is <span class="math-container">$\Omega(d)$</span> (see Section 3 of <a href="https://www.theoryofcomputing.org/articles/v004a006/v004a006.pdf" rel="nofollow noreferrer">this paper</a>), and it can be solved by approximating <span class="math-container">$x_i = \langle x, e_i\rangle$</span> up to any multiplicative factor where <span class="math-container">$e_i$</span> is the vector with <span class="math-container">$1$</span> in the <span class="math-container">$i$</span>-th coordinate and <span class="math-container">$0$</span>'s everywhere else. So your problem has <span class="math-container">$\Theta(d)$</span> randomized one-way communication complexity for <span class="math-container">$r=1$</span>. </p>

CC BY-SA 4.0
2019-04-11T18:04:01.503Z
Thanks! I think [this paper](http://www.cs.cmu.edu/afs/cs/user/dwoodruf/www/psw14.pdf) 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
CC BY-SA 4.0
2019-04-11T01:19:23.477Z
2019-04-11T01:19:23.477Z
Sasho Nikolov
<p>Alice has a vector <span class="math-container">$x \in [r]^d$</span> and Bob has <span class="math-container">$y \in [r]^d$</span>, where <span class="math-container">$[r] \stackrel{\rm def}{=} \{0,1,\dots,r\}$</span>. Alice send a message <span class="math-container">$M(x)$</span> to Bob and Bob wants to estimate the inner product <span class="math-container">$\left&lt;x,y\right&gt;$</span> with multiplicative error <span class="math-container">$\epsilon$</span> with probability <span class="math-container">$1 - \delta$</span>.</p>

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

CC BY-SA 4.0
2019-04-10T20:54:00.100Z
What is $[r]$?  Do you mean, e.g., $[0,r]$?
Neal Young
CC BY-SA 4.0
2019-04-10T20:55:25.707Z
I should have clarified, it means integers from 0 to r.
Dawei Huang
CC BY-SA 4.0
2019-04-10T20:57:38.680Z
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
CC BY-SA 4.0
2019-04-10T21:06:15.883Z
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
CC BY-SA 4.0
2019-04-10T21:39:26.673Z
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
CC BY-SA 4.0
2019-04-10T21:50:30.713Z
FWIW the case $r=1$ and $y$ restricted to vectors with a single non-zero coordinate is similar to the problem that Bloom filters solve (compress a bit vector $x$ into a small bit string $M(x)$ so that, using only $M(x)$, one can confidently test, for a given $i$, whether $x_i=1$).  If $x$ has, say, $d/2$ bits set, I think such a Bloom filter requires $\Omega(d)$ bits.  On the other hand Bloom filters don't have false negatives.
Neal Young
CC BY-SA 4.0
2019-04-10T22:05:51.187Z
may be relevant: https://cstheory.stackexchange.com/questions/31656/one-way-randomized-communication-complexity-of-approximate-hamming-distance
Neal Young
CC BY-SA 4.0
2019-04-11T17:57:01.833Z
So it is not necessary for Alice to approximate every $x_i$, or rather it depends on a lower bound on the inner product? I think the case when $r = 1$ is the problem of estimating set intersection and there is an optimal $\Omega(d/(T\epsilon^2))$ lower bound according to [this paper](http://www.cs.cmu.edu/afs/cs/user/dwoodruf/www/psw14.pdf). I am interested in how it extends to general $r$.
Dawei Huang
<reference-request><communication-complexity>
Estimating inner product over $[r]^d$
Dawei Huang
# Estimating inner product over $[r]^d$

(Asked by: username_0 on 2019-04-10)

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

**Tags:** reference-request, communication-complexity

> **Comments:**
> **username_1**: What is $[r]$?  Do you mean, e.g., $[0,r]$?  
> **username_0**: I should have clarified, it means integers from 0 to r.  
> **username_1**: 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$?  
> **username_0**: 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$.  
> **username_1**: 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$.  
> **username_1**: FWIW the case $r=1$ and $y$ restricted to vectors with a single non-zero coordinate is similar to the problem that Bloom filters solve (compress a bit vector $x$ into a small bit string $M(x)$ so that, using only $M(x)$, one can confidently test, for a given $i$, whether $x_i=1$).  If $x$ has, say, $d/2$ bits set, I think such a Bloom filter requires $\Omega(d)$ bits.  On the other hand Bloom filters don't have false negatives.  
> **username_1**: may be relevant: https://cstheory.stackexchange.com/questions/31656/one-way-randomized-communication-complexity-of-approximate-hamming-distance  
> **username_0**: So it is not necessary for Alice to approximate every $x_i$, or rather it depends on a lower bound on the inner product? I think the case when $r = 1$ is the problem of estimating set intersection and there is an optimal $\Omega(d/(T\epsilon^2))$ lower bound according to [this paper](http://www.cs.cmu.edu/afs/cs/user/dwoodruf/www/psw14.pdf). I am interested in how it extends to general $r$.  

---

## 1 answers

### Answer by username_2 on 2019-04-11. Score: 3 | Accepted answer

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](https://www.theoryofcomputing.org/articles/v004a006/v004a006.pdf)), 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$.

> **Comments:**
> **username_0**: Thanks! I think [this paper](http://www.cs.cmu.edu/afs/cs/user/dwoodruf/www/psw14.pdf) 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$.  

---

