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…