201 citations · 235 across the 24 of their papers we have counts for
4 papers · 1 filter
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…
Hilbert Functions and Low-Degree Randomness Extractors
Alexander Golovnev, Zeyu Guo, Pooya Hatami +2
For , consider the linear space of restrictions of degree- polynomials to . The Hilbert function of , denoted , is the…
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…
Structure in Communication Complexity and Constant-Cost Complexity Classes
Hamed Hatami, Pooya Hatami
Several theorems and conjectures in communication complexity state or speculate that the complexity of a matrix in a given communication model is controlled by a related analytic o…