Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
Communication complexity of point-line incidences over the reals
Marcel K. Goh, Hamed Hatami
We construct a point-line incidence problem over the reals whose randomized communication complexity is constant, but whose deterministic communication complexity is linear even wh…
cs.CC2026
Lower Bounds for Approximate Sign Rank
Riju Bindua, Hamed Hatami, Hasti Karimi +1
We prove new upper and lower bounds on -approximate sign-rank, a relaxation of sign-rank introduced by Chornomaz, Moran, and Waknine (STOC 2025). We show that every …
cs.CC2024
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…