Discrepancy of geometric incidences
Computational ComplexityDiscrete Mathematics
Summary
The authors study how well one can color points red or blue so that any shape made by certain algebraic equations has almost equal numbers of red and blue points inside it. They improve on previous bounds by showing a better way to color points that reduces this imbalance (discrepancy) for sets defined by shapes of limited complexity. They also show that in some cases, you cannot do better than certain limits for discrepancy with hyperplanes. Additionally, their methods have applications in communication complexity, especially in understanding differences between randomized and deterministic communication models.
Authors
Azem Adibelli, István Tomon
Abstract
We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every $n$-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most $D$ and degree at most $k$ has discrepancy at most $n^{\frac12-\frac{1}{2(D+1)}-\varepsilon}$ for some $\varepsilon=\varepsilon(D,k)>0$. This gives a polynomial improvement over the straightforward VC-dimension bound $\tilde O(n^{\frac12-\frac{1}{2(D+1)}})$. In the opposite direction, we construct $n$-point sets in $\mathbb R^d$ whose discrepancy with respect to hyperplanes is $\tildeΩ(n^{\frac12-\frac{1}{d+1}}),$ extending the point-line discrepancy lower bound of Chazelle and Lvov. We present further applications of our methods in communication complexity, concerning separation between randomized communication cost and deterministic communication cost with access to equality oracle.