The Strength of Equality Oracles in Communication
The Strength of Equality Oracles in Communication
复制标题
DOI：
10.4230/lipics.itcs.2023.89
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
T. Pitassi;Morgan Shirley;A. Shraibman
中科院分区：
文献类型：
--
作者：
T. Pitassi;Morgan Shirley;A. Shraibman
众所周知，随机通信协议比确定性协议更强大。特别是等式函数需要Ω(n)确定性通信复杂度，但具有高效的随机化协议。Chattopadhyay， Lovett和Vinyals之前的工作表明，随机通信严格强于配备了平等预言器的确定性协议所能解决的问题。尽管存在这种分离，但我们还远远不能理解在通信复杂性的背景下，平等神谕的确切力量。本文主要研究了非确定性通信，该通信是梅林-亚瑟通信的一个子类。我们通过证明在不确定性等式模型中不能使用次线性通信计算整数内积函数，证明了这种包含是严格的，即使在有界误差随机情况下也能有效地计算。为了证明这一点，我们给出了不确定性等式模型的一个新的矩阵理论表征：具体来说，该模型与基于Hambardzumyan、Hatami和Hatami的块矩阵的覆盖数以及Gamma-2分解范数的自然变体之间存在紧密联系。对于具有相等神谕的明确的不确定性模型，也显示了类似的等价。从这些证明中产生了一个额外的结果：对于所研究的通信模型，单个Equality oracle调用就足够了，而不会失去一般性。我们的结果允许我们证明在存在相等神谕的情况下确定性和明确的非确定性之间的分离。这与Yannakakis的结果相反，Yannakakis的结果表明这些模型是多项式相关的，没有神谕。我们沿着这个方向提出了一些有趣的开放性问题，以及我们工作中产生的其他问题。
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 nondeter-minism 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.