Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-050 | 18th April 2023 18:26

Communication complexity of half-plane membership



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.

ISSN 1433-8092 | Imprint