201 citations · 235 across the 24 of their papers we have counts for
13 papers · 1 filter
Exponential Correlation Bounds for Polynomials
Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee +3
We prove that the XOR of majorities on disjoint blocks of bits has correlation at most with every Boolean-valued degree- polynomial over an arbit…
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…
A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami
We refute the Probabilistic Universal Graph Conjecture of Harms, Wild, and Zamaraev, which states that a hereditary graph property admits a constant-size probabilistic universal gr…