标题： 等式比常数成本通信弱得多 显示英文标题

标题： Equality is Far Weaker than Constant-Cost Communication

摘要： 我们展示了一个$n$位通信问题，该问题具有常数成本的随机协议，但需要$n^{\Omega(1)}$个确定性（甚至非确定性）查询来使用等价 oracle。 因此，即使常数成本的随机协议也不能通过使用等价 oracle 来高效地“去随机化”。 这改进了几个最近的结果，并回答了 Hatami 和 Hatami（SIGACT News 2024）调查中的一个问题。 它还给出了 Fang、Göös、Harms 和 Hatami（STOC 2025）主要结果的一个显著更简单且定量更优的证明，即常数成本的通信不能归约到$k$-汉明距离层次结构。 显示英文摘要

摘要： We exhibit an $n$-bit communication problem with a constant-cost randomized protocol but which requires $n^{\Omega(1)}$ deterministic (or even non-deterministic) queries to an Equality oracle. Therefore, even constant-cost randomized protocols cannot be efficiently "derandomized" using Equality oracles. This improves on several recent results and answers a question from the survey of Hatami and Hatami (SIGACT News 2024). It also gives a significantly simpler and quantitatively superior proof of the main result of Fang, G\"o\"os, Harms, and Hatami ( STOC 2025), that constant-cost communication does not reduce to the $k$-Hamming Distance hierarchy.