No Constant-Cost Protocol for Point--Line Incidence

Mika Göös, Nathaniel Harms, Florian K. Richter +1

Alice and Bob are given $n$-bit integer pairs $(x,y)$ and $(a,b)$, respectively, and they must decide if $y=ax+b$. We prove that the randomised communication complexity of this Poi…