Communication Complexity and Discrepancy of Halfplanes

Manasseh Ahmed, Tsun-Ming Cheung, Hamed Hatami, Kusha SareenSoCG 2024 · OpenReview

TL;DR

This paper tackles the "halfplane membership problem" in communication complexity, where Alice has a halfplane and Bob has a point, and they need to determine if the point is in the halfplane. The authors establish tight bounds for this problem's communication discrepancy, showing it's surprisingly small (O(n^{-1/6} log^{3/2} n)) for specific input distributions, while also proving a general lower bound (Ω(n^{-1/4} log^{-1} n)) for any set of points and halfplanes. This work bridges theoretical computer science concepts like discrepancy theory and communication complexity, offering insights into the fundamental limits of distributed computation.

What Problem Does This Paper Address?

The core problem is the "halfplane membership problem" in the realm of communication complexity. Imagine Alice knows a line defining a halfplane (e.g., $x_1y_1 + y_2 \ge x_2$), and Bob knows a point $(y_1, y_2)$. Their goal is to figure out if Bob's point lies within Alice's halfplane, but they can only communicate a limited amount of information. The "discrepancy" of this problem quantifies how "irregular" or "unbalanced" the outcomes are across different possible inputs and communication strategies. A low discrepancy means that even with optimal strategies, there's a fundamental limit to how well the players can agree on the outcome for all possible inputs. The paper aims to precisely characterize this discrepancy for the halfplane membership problem, bridging a gap between theoretical bounds and practical implications for distributed decision-making.

Methods

The paper employs a combination of techniques from communication complexity and discrepancy theory. A key contribution is establishing an upper bound on the communication discrepancy of the halfplane membership problem. This is achieved through a sophisticated construction of a "hard distribution" over the inputs and the use of Fourier analysis on cyclic groups. This method allows them to analyze the "invariance under shift" property of certain functions, which is crucial for bounding the discrepancy.

On the lower bound side, the authors leverage connections to "hereditary discrepancy" and the $\psi_2$ norm, established in prior work by Matoušek, Nikolov, and Talwar. By relating communication discrepancy to these established measures, they can translate existing results from geometric discrepancy theory into lower bounds for their specific problem. A crucial technical tool is Proposition 5, which bridges the gap between discrepancy in boolean matrices and sign matrices, allowing them to apply results from one domain to the other.

Datasets

Not discussed in the paper. The paper deals with theoretical bounds on communication complexity and discrepancy, not empirical evaluation on specific datasets. The "datasets" are implicitly defined by the input distributions and the sets of points and halfplanes considered.

Key Insights and Ideas

  • Tight Bounds for a Fundamental Problem: The paper provides nearly matching upper and lower bounds for the discrepancy of the halfplane membership problem, settling a significant question in communication complexity.
  • Bridging Theory: The work elegantly connects concepts from discrepancy theory (geometric and combinatorial) with communication complexity, demonstrating how insights from one field can illuminate problems in another.
  • The Power of Fourier Analysis: The use of Fourier analysis on cyclic groups is a central technical tool for deriving the upper bound, showcasing its utility in analyzing communication protocols and distributions.
  • Hereditary Discrepancy as a Bridge: The paper highlights the importance of hereditary discrepancy and its relationship with the $\psi_2$ norm as a powerful tool for deriving lower bounds in communication complexity.
  • Sign-Rank vs. Discrepancy: The work contributes to the ongoing research on the separation between sign-rank and discrepancy, showing that even for problems with low sign-rank (like the one studied), discrepancy can still be significant, though their results narrow this gap.

Key Results

  • Upper Bound: The communication discrepancy of the halfplane membership problem for inputs chosen from $[m] \times [m^2]$ is shown to be $O(n^{-1/6} \log^{3/2} n)$, where $n = m^3$.
  • Lower Bound: For any set of $n$ points and $n$ halfplanes, the communication discrepancy is at least $\Omega(n^{-1/4} \log^{-1} n)$.
  • Randomized Communication Complexity: The upper bound on discrepancy implies a lower bound of $\Omega(\log n)$ for the randomized communication complexity of the halfplane membership problem. This means that even with randomness, at least $\Omega(\log n)$ bits of communication are needed.
  • Sign-Rank Connection: The paper demonstrates that for matrices with bounded sign-rank, their discrepancy can be significantly separated from the trivial $\Omega(n^{-1/2})$ bound.

Limitations and Future Work

  • Specific Input Distribution: The tight upper bound of $O(n^{-1/6} \log^{3/2} n)$ is achieved for a specific, carefully constructed distribution of inputs. The discrepancy for arbitrary distributions might be different, though the general lower bound provides a baseline.
  • Generalization: While the paper focuses on the 2D halfplane membership problem, future work could explore higher dimensions or variations of the problem.
  • Technical Complexity: The proofs, particularly for the upper bound, are technically involved, relying on advanced Fourier analysis and number theory estimates. Simplifying these proofs or finding alternative approaches could be a direction for future research.
  • Connection to Learning Theory: The paper mentions connections to learning theory (e.g., linear classifiers, margin). Further exploration of these links could yield new insights.

Summary updated

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₁y₁+y₂ ≥ x₂, where the first player knows (x₁,x₂) and the second player knows (y₁,y₂). Denoting n = m³, we show that when the inputs are chosen from [m] × [m²], 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šek, Nikolov, and Tawler (IMRN 2020) and a classical result of Matoušek (Discrete Comput. Geom. 1995), we show that the communication discrepancy of every set of n points and n halfplanes is at least Ω(n^{-1/4} log^{-1} n).
BibTeX
@inproceedings{ahmed2024communication,
  author = {Manasseh Ahmed and Tsun-Ming Cheung and Hamed Hatami and Kusha Sareen},
  title = {{Communication Complexity and Discrepancy of Halfplanes}},
  booktitle = {SoCG},
  year = {2024},
  url = {https://openreview.net/forum?id=7FyRQWK0R5},
}
Figure