TR23-050 Authors: Manasseh Ahmed, TsunMing Cheung, Hamed Hatami, Kusha Sareen

Publication: 19th April 2023 15:14

Downloads: 116

Keywords:

We study the randomized communication complexity of the following problem. Alice receives the integer coordinates of a point in the plane, and Bob receives the integer parameters of a half-plane, and their goal is to determine whether Alice's point belongs to Bob's half-plane.

This communication task corresponds to determining whether $x_1y_1+y_2\geq x_2$, where the first player knows $(x_1,x_2) \in [n]^2$ and the second player knows $(y_1,y_2) \in [n]^2$. We prove that its randomized communication complexity is $\Omega(\log n)$.

Our lower bound extends a recent result of Hatami, Hosseini, and Lovett (CCC '20 and ToC '22) regarding the largest possible gap between sign-rank and randomized communication complexity.