Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-050 | 20th March 2024 17:24

Communication Complexity and Discrepancy of Halfplanes

RSS-Feed




Revision #1
Authors: Manasseh Ahmed, Tsun-Ming Cheung, Hamed Hatami, Kusha Sareen
Accepted on: 20th March 2024 17:24
Downloads: 31
Keywords: 


Abstract:

We study the discrepancy of the following communication problem. Alice receives a halfplane, and Bob receives a point in the plane, and their goal is to determine whether Bob's point belongs to Alice's halfplane. This communication task corresponds to determining whether $x_1y_1+y_2\geq x_2$, where the first player knows $(x_1,x_2)$ and the second player knows $(y_1,y_2)$.

Denoting $n=m^3$, we show that when the inputs are chosen from $[m] \times [m^2]$, the communication discrepancy of the above problem is $O(n^{-1/6} \log^{3/2}n)$.

On the other hand, through the connections to the notion of hereditary discrepancy by Matou\v{s}ek, Nikolov, and Tawler (IMRN 2020) and a classical result of Matou\v{s}ek (Discrete Comput. Geom. 1995), we show that the communication discrepancy of every set of $n$ points and $n$ halfplanes is at least $\Omega(n^{-1/4} \log^{-1} n)$.



Changes to previous version:

New parts in connection with discrepancy theory, and revised title.


Paper:

TR23-050 | 18th April 2023 18:26

Communication complexity of half-plane membership


Abstract:

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