Showing 2024Show all
3 papers · 1 filter
cs.CC2024
Better Boosting of Communication Oracles, or Not
Nathaniel Harms, Artur Riazanov
Suppose we have a two-party communication protocol for which allows the parties to make queries to an oracle computing ; for example, they may query an Equality oracle. To t…
cs.CC2024
Constant-Cost Communication is not Reducible to k-Hamming Distance
Yuting Fang, Mika Göös, Nathaniel Harms +1
Every known communication problem whose randomized communication cost is constant (independent of the input size) can be reduced to -Hamming Distance, that is, solved with a con…
cs.CC2024
No Complete Problem for Constant-Cost Randomized Communication
Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms +1
We prove that the class of communication problems with public-coin randomized constant-cost protocols, called , does not contain a complete problem. In other words, there is…