Communication complexity of point-line incidences over the reals
For communication complexity theorists, this provides the optimal separation between randomized and deterministic communication with equality oracle, resolving a question about constant sign rank.
The paper constructs a point-line incidence problem over the reals with constant randomized communication complexity but linear deterministic complexity even with an equality oracle, achieving the strongest possible separation. It also improves a previous logarithmic lower bound to an optimal linear separation for a related question on sign rank.
We construct a point-line incidence problem over the reals whose randomized communication complexity is constant, but whose deterministic communication complexity is linear even when the players have access to an equality oracle. This is the strongest possible separation between these two measures, and it improves on an earlier $O(1)$-versus-$Ω(\sqrt{n})$ separation of Göös, Harms, and Riazanov. Because point-line incidence problems have constant sign rank, our construction also bears on a question of Harms and Zamaraev, who asked whether constant sign rank together with constant randomized communication complexity forces constant equality-oracle complexity. This was already refuted by Göös, Harms, Imbach, and Sokolov with a logarithmic lower bound; our example improves the separation to linear, which is optimal. The proof draws on a construction in the recent disproof of the sum-product conjecture over the reals by Bloom, Sawin, Schildkraut, and Zhelezov, using totally real number fields of large degree and small discriminant.