2 papers
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…