Randomized communication complexity of or-of-equalities

Question

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 [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) lift using $\wedge$, not $\oplus$ (a.k.a. equality).

Thanks!

Noah

Answer 1

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 <x,r> 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 <x',r>=<x,r>. 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.)