It is well-known that randomized communication protocols are more powerful than deterministic protocols. In particular the Equality function requires $\Omega(n)$ deterministic communication complexity but has efficient randomized protocols. Previous work of Chattopadhyay, Lovett and Vinyals shows that randomized communication is strictly stronger than what can be solved by deterministic protocols equipped with an Equality oracle. Despite this separation, we are far from understanding the exact strength of Equality oracles in the context of communication complexity.

In this work we focus on nondeterminisic communication equipped with an Equality oracle, which is a subclass of Merlin-Arthur communication. We show that this inclusion is strict by proving that the previously-studied Integer Inner Product function, which can be efficiently computed even with bounded-error randomness, cannot be computed using sublinear communication in the nondeterministic Equality model. To prove this we give a new matrix-theoretic characterization of the nondeterministic Equality model: specifically, there is a tight connection between this model and a covering number based on the blocky matrices of Hambardzumyan, Hatami, and Hatami, as well as a natural variant of the Gamma-2 factorization norm. Similar equivalences are shown for the unambiguous nondeterministic model with Equality oracles. A bonus result arises from these proofs: for the studied communication models, a single Equality oracle call suffices without loss of generality.

Our results allow us to prove a separation between deterministic and unambiguous nondeterminism in the presence of Equality oracles. This stands in contrast to the result of Yannakakis which shows that these models are polynomially-related without oracles. We suggest a number of intriguing open questions along this direction of inquiry, as well as others that arise from our work.