ECCC-Report TR23-050https://eccc.weizmann.ac.il/report/2023/050Comments and Revisions published for TR23-050en-usWed, 19 Apr 2023 15:14:07 +0300
Paper TR23-050
| Communication complexity of half-plane membership |
Hamed Hatami,
TsunMing Cheung,
Manasseh Ahmed,
Kusha Sareen
https://eccc.weizmann.ac.il/report/2023/050We 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.
Wed, 19 Apr 2023 15:14:07 +0300https://eccc.weizmann.ac.il/report/2023/050