License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.89
URN: urn:nbn:de:0030-drops-175927
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17592/
Pitassi, Toniann ;
Shirley, Morgan ;
Shraibman, Adi
The Strength of Equality Oracles in Communication
Abstract
It is well-known that randomized communication protocols are more powerful than deterministic protocols. In particular the Equality function requires Ω(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.
BibTeX - Entry
@InProceedings{pitassi_et_al:LIPIcs.ITCS.2023.89,
author = {Pitassi, Toniann and Shirley, Morgan and Shraibman, Adi},
title = {{The Strength of Equality Oracles in Communication}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {89:1--89:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17592},
URN = {urn:nbn:de:0030-drops-175927},
doi = {10.4230/LIPIcs.ITCS.2023.89},
annote = {Keywords: Factorization norm, blocky rank, Merlin-Arthur}
}
|
Keywords: |
|
Factorization norm, blocky rank, Merlin-Arthur |
|
Collection: |
|
14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
01.02.2023 |
