Showing cs.CCShow all
2 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 $m \times n…