<p>We can directly reduce Set Disjointness to OR of Equalities. (This immediately implies an <span class="math-container">$\Omega(n)$</span> lower bound.) I think the proof is basically folklore.</p>
<p>For a vector <span class="math-container">$A$</span> and <span class="math-container">$B$</span> of length <span class="math-container">$n$</span>,
replace each 0 of <span class="math-container">$A$</span> with the string <span class="math-container">$00$</span>, replace each 0 of <span class="math-container">$B$</span> with the string <span class="math-container">$01$</span>, and replace the 1s in <em>both</em> strings with the string <span class="math-container">$11$</span>.</p>
<p>Observe the vectors are not orthogonal / sets are not disjoint if and only if the OR of Equality is true.</p>
<p>By the way, I see how to get an <span class="math-container">$O(n \log n)$</span> randomized upper bound by hashing the strings to <span class="math-container">$O(\log n)$</span> bits, but I don't immediately see how to get a matching <span class="math-container">$O(n)$</span> upper bound.</p>
<hr />
<p>EDIT: The following seems to yield an <span class="math-container">$O(n)$</span> upper bound with public randomness. Alice picks a random r and computes &lt;x,r&gt; mod 2 for each of her strings x, sending an n bit vector. Bob responds with an n bit vector indicating which of his corresponding x' have &lt;x',r&gt;=&lt;x,r&gt;. In expectation, the number of ones (call it B) in Bob's string is (n-k)/2+k, where k is the number of string pairs that are equal. They repeat this process, but <em>only</em> with the strings that Bob reported &quot;agreement&quot; with, so in the next round Alice and Bob will only exchange 2B bits. We repeat until the number of ones in Bob's string does <em>not</em> go down by at least 1/3 (say) from one round to the next, or when Bob's string is all-zeroes. In the first case, we guess that it's a yes instance (k &gt; 0) and in the second case we conclude it's a no instance. For a no instance, the total communication before making a decision is expected to be about 2n+n+n/2+...+1, or O(n). (If we are talking &quot;too much&quot;, we may guess that it's actually a yes instance.)</p>

CC BY-SA 4.0
2022-08-11T15:35:04.573Z
Neat! Notes to self: 1) could pick any $3$ distinct strings for the encoding, 2) this is $n$ equalities on $2$ bits.
Noah Singer
CC BY-SA 4.0
2022-08-11T14:57:32.977Z
2022-08-11T18:30:16.913Z
2022-08-11T18:30:16.913Z
Ryan Williams
<p>Is there a reference for a randomized communication lower bound for the following problem: <span class="math-container">$\textsf{Or-of-Equalities} : \{0,1\}^{n^2} \times \{0,1\}^{n^2} \to \{0,1\}$</span> defined by <span class="math-container">$f(x,y)=1$</span> iff there is some <span class="math-container">$i \in [n]$</span> s.t. <span class="math-container">$x_{(i-1)n+1}\cdots x_{in} = y_{(i-1)n+1} \cdots y_{in}$</span>? The &quot;unparallelized&quot; version is simply the <span class="math-container">$\textsf{Equality}$</span> function on <span class="math-container">$n$</span> bits, which has <span class="math-container">$\Theta(\log n)$</span> randomized communication complexity. I would hope that the bound is something like <span class="math-container">$\Omega(n)$</span> :)</p>
<p>For context, I was thinking about the <span class="math-container">$\textsf{Sink}$</span> function used by Chattopadhyay, Mande, and Sherif to <a href="https://eccc.weizmann.ac.il/report/2018/176/" rel="nofollow noreferrer">disprove the log-approximate-rank conjecture</a> [J. ACM '20]. This function is almost the same, except each pair of equalities overlaps in a single input coordinate (for which the required value differs between the two equalities). They get an <span class="math-container">$\Omega(n)$</span>(-ish?) bound using the corruption method, which may also go through for this other function --- I'm not sure. The function also resembles <span class="math-container">$\textsf{Tribes}$</span> - except when you look up randomized communication complexity of <span class="math-container">$\textsf{Tribes}$</span>, the results (e.g. <a href="http://dx.doi.org/10.1145/780542.780640" rel="nofollow noreferrer">Jayram, Kumar, and Sivakumar, STOC '03</a>) lift using <span class="math-container">$\wedge$</span>, not <span class="math-container">$\oplus$</span> (a.k.a. equality).</p>
<p>Thanks!</p>
<p>Noah</p>

<communication-complexity>
Randomized communication complexity of or-of-equalities
Noah Singer
# Randomized communication complexity of or-of-equalities

(Asked by: username_0 on 2022-08-11)

Is there a reference for a randomized communication lower bound for the following problem: $\textsf{Or-of-Equalities} : \{0,1\}^{n^2} \times \{0,1\}^{n^2} \to \{0,1\}$ defined by $f(x,y)=1$ iff there is some $i \in [n]$ s.t. $x\_{(i-1)n+1}\cdots x\_{in} = y\_{(i-1)n+1} \cdots y\_{in}$? The "unparallelized" version is simply the $\textsf{Equality}$ function on $n$ bits, which has $\Theta(\log n)$ randomized communication complexity. I would hope that the bound is something like $\Omega(n)$ :)

For context, I was thinking about the $\textsf{Sink}$ function used by Chattopadhyay, Mande, and Sherif to [disprove the log-approximate-rank conjecture](https://eccc.weizmann.ac.il/report/2018/176/) [J. ACM '20]. This function is almost the same, except each pair of equalities overlaps in a single input coordinate (for which the required value differs between the two equalities). They get an $\Omega(n)$(-ish?) bound using the corruption method, which may also go through for this other function --- I'm not sure. The function also resembles $\textsf{Tribes}$ - except when you look up randomized communication complexity of $\textsf{Tribes}$, the results (e.g. [Jayram, Kumar, and Sivakumar, STOC '03](http://dx.doi.org/10.1145/780542.780640)) lift using $\wedge$, not $\oplus$ (a.k.a. equality).

Thanks!

Noah

**Tags:** communication-complexity

---

## 1 answers

### Answer by username_1 on 2022-08-11. Score: 8 | Accepted answer

We can directly reduce Set Disjointness to OR of Equalities. (This immediately implies an $\Omega(n)$ lower bound.) I think the proof is basically folklore.

For a vector $A$ and $B$ of length $n$,
replace each 0 of $A$ with the string $00$, replace each 0 of $B$ with the string $01$, and replace the 1s in *both* strings with the string $11$.

Observe the vectors are not orthogonal / sets are not disjoint if and only if the OR of Equality is true.

By the way, I see how to get an $O(n \log n)$ randomized upper bound by hashing the strings to $O(\log n)$ bits, but I don't immediately see how to get a matching $O(n)$ upper bound.

---

EDIT: The following seems to yield an $O(n)$ upper bound with public randomness. Alice picks a random r and computes  mod 2 for each of her strings x, sending an n bit vector. Bob responds with an n bit vector indicating which of his corresponding x' have =. In expectation, the number of ones (call it B) in Bob's string is (n-k)/2+k, where k is the number of string pairs that are equal. They repeat this process, but *only* with the strings that Bob reported "agreement" with, so in the next round Alice and Bob will only exchange 2B bits. We repeat until the number of ones in Bob's string does *not* go down by at least 1/3 (say) from one round to the next, or when Bob's string is all-zeroes. In the first case, we guess that it's a yes instance (k > 0) and in the second case we conclude it's a no instance. For a no instance, the total communication before making a decision is expected to be about 2n+n+n/2+...+1, or O(n). (If we are talking "too much", we may guess that it's actually a yes instance.)

> **Comments:**
> **username_0**: Neat! Notes to self: 1) could pick any $3$ distinct strings for the encoding, 2) this is $n$ equalities on $2$ bits.  

---

