The strength of equality oracles in communication

Christian Engels November 21, 2022 [TCS, Communication Complexity]

The Strength of Equality Oracles in communiucation

It is known that equality in communication complexity is the "hardest" function, i.e., needing $\Omega(n)$ bits of communication.
However, for randomized communication, we need only $O(1)$ many bits.
This gives rise to the question: What total function can be efficiently computed in a communication model with oracle access to Equality?
- Notice that only function with asymptotic less than $O(n)$ are interesting.
- In some sense, we allow algorithms to use randomness but only in the restricted sense that we can solve equality.
Some functions can be solved with equality such as greater-than.
But equality cannot simulate all randomized protocols Chattopadhyay, Lovett, Vinyals - Equality alone does not simulate randomness
Hence, Equality is not just all of randomized communication complexity in a complexity class sense.
Questions:
- What models can be computed if we give stronger communication model (than randomized) as the base with equality oracle access.
- What happens if we restrict the reductions in (CLV) to be many-one reductions?
- Non-deterministic communication for which no linear bounds are known.

A blocky matrix is essentially a blowup of an identity matrix with some rows and columns deleted, duplicated or permuted or with zero rows added.
Blocky number is the minimum number of blocky matrices needed to cover a matrix.
Similar with blocky partition number.
We will omit the cc to denote communication complexity, as we will only talk about communication complexity in this.
UP is the unambigious nondeterministic model where a prover sends player a witness string after which the players proceed deterministically.
NP^EQ are $2^m$ many P^EQ protocols and the result is the OR of all these executions with EQ oracle access.
$\gamma_2(A) = \min_{X,Y XY^T =A} r(X)r(Y)$ where $r$ is the maximum $l_2$ norm of any row.

UP^Eq $\leq \log \chi_1(A) \leq O($UP^Eq$ \log n)$ where $\chi_1$ is the minimal $r$ such that $A$ can be expressed as the sum of blocky matrices.
NP^Eq $\leq \log C_1(A) \leq O($NP^Eq$ \log n)$ where $C_1$ is the minium number of blocky matrices such that $A$ is the entry wise OR of these matrices.