CS Paper Radar

Discrepancy of geometric incidences

Azem Adibelli, István Tomon

cs.CC math.COcs.DMmath.MG ·submitted 2026-08-28 14:05 UTC · v1
theory

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.

Comment
32 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Sharp topological overlap in every dimension

cs.CG math.CO ·2026-11-19 ·Sergey Norin
theory similarity 0.65
Abstract

For a positive integer $d$ let $c_d^{\mathrm{top}}$ (resp. $c_d^{\mathrm{aff}}$) be the maximum $c$ such that, for every continuous (resp. affine) map from the $n$-dimensional simplex $Δ^n$ to $\mathbb{R}^d$, some point of $\mathbb{R}^d$ lies in the images of at least $(c-o(1))\binom{n+1}{d+1}$ of the $d$-dimensional faces, as $n\to\infty$. We show that \[ c_d^{\mathrm{top}}=c_d^{\mathrm{aff}}=\frac{(d+1)!}{(d+1)^{d+1}}. \] The second equality confirms a conjecture of Bukh, Matoušek, and Nivasch, who established the upper bound. The proof was found by GPT-6 Astra, following the directions of the author.

0.31

Bourgain's Theorem for a Union of Euclidean Metric Spaces

cs.DS cs.CGmath.MG ·2026-11-05 ·Dimitar Chakarov, Sepideh Mahabadi, Yury Makarychev, Ali Vakilian
theory similarity 0.63
Abstract · 33 pages

We study the distortion of embedding a union of $k$ Euclidean sets into Euclidean space. We show that a union of $k$ Euclidean sets can be embedded with distortion at most $O(k^{1.128} \log k)$, independent of the number of points. This is an exponential improvement over the previous best known upper bound of $2^{O(k)}$ obtained by iterating the result of Makarychev and Makarychev (2016) for the special case $k = 2$. Surprisingly, with the additional assumption that each Euclidean set remains Euclidean when we adjoin any other two points, we can obtain an asymptotically tight distortion of $O(\log k)$, thus, providing a generalization of Bourgain's Theorem (1985). Along the way, we also show that the distortion of the union can be upper bounded by $O(\log k)$ times the maximum of the Lipschitz extension constants of individual Euclidean sets.

0.22

Resolving Tusnády's Problem

cs.CG math.CAcs.DSmath.CO ·2026-11-04 ·Nicola Wengiel
theory similarity 0.62
Abstract · 33 pages

We prove a lower bound of $Ω_d((\log N)^{d-1/2})$ for the worst-case combinatorial discrepancy of $N$-point sets with respect to anchored boxes in every fixed dimension $d\ge3$. Together with Nikolov's upper bound of the same order and Wei's planar lower bound, this settles Tusnády's problem: the discrepancy of axis-parallel boxes is $Θ_d((\log N)^{d-1/2})$ in every fixed dimension $d\ge2$. The proof combines smoothed product test functions, sampling discretization, and an entropy argument for conditioned Gaussian vectors.

0.15

Almost Optimal Lower Bounds under Almost ETH for Approximating Euclidean k-means

cs.CG cs.CCcs.DSstat.ML ·2026-11-11 ·Karthik C. S., Dor Minzer
theory similarity 0.62
Abstract

In the Euclidean $k$-means problem, we are given a set of $n$ points in $\mathbb{R}^d$, and the goal is to find $k$ representative points in space so as to minimize the sum of the squared distances from each point to its closest representative. Algorithmically, de la Vega, Karpinski, Kenyon, and Rabani [STOC'03] and Kumar, Sabharwal, and Sen [JACM'10] obtain a $(1+\varepsilon)$-approximation for high-dimensional Euclidean $k$-means in time $2^{(k/\varepsilon)^{O(1)}} \cdot dn^{O(1)}$, which was subsequently improved to $2^{\tilde{O}(k/\varepsilon)} + O(ndk)$ by Feldman, Monemizadeh, and Sohler [SoCG'07]. On the lower-bound side, a recent work of Cohen-Addad, Karthik, Saulpic, and Schwiegelshohn [SoCG'26] proposed the Exponential Time for Expanders Hypothesis (XXH), which asserts exponential-time hardness for $(1+\varepsilon)$-approximating Vertex Cover on vertex expanders, and used it to prove nearly matching running time lower bound whenever $k=\tildeω(1/\varepsilon)$. We observe that XXH does not hold in the parameter regime needed for the above result, and show how to repair their reduction under a more standard assumption. More precisely, we show that assuming the Almost Exponential Time Hypothesis for 3-SAT (Almost ETH), for every constant $β\in(0,1)$, Euclidean $k$-means in $\mathbb{R}^d$ has no $(1+\varepsilon)$-approximation algorithm running in time $2^{(k/\varepsilon)^{1-β}}\text{poly}(n,d)$, whenever $k=\tildeω(1/\varepsilon)$. By modifying the construction, we also obtain a similar result for approximating the Euclidean $k$-median problem.

0.12

The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

cs.CG cs.DSmath.MGmath.PR ·2026-08-13 ·Vishesh Jain
theory similarity 0.61
Abstract · 13 pages; comments welcome!

The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameters $n,d, \varepsilon$ is \[ Θ\left(\min\left\{d,n-1,\frac{\log(2+\varepsilon^2n)}{\varepsilon^2}\right\}\right). \] We resolve this conjecture in the affirmative. In fact, we prove the stronger statement that the upper bound is attained by a linear map. The matching lower bound, due to Larsen--Nelson and Alon--Klartag, holds even for nonlinear embeddings.

0.10

New Quantitative Bounds for the $(p,q)$-Theorem for Unions of Convex Sets

cs.CG math.CO ·2026-08-13 ·Chaya Keller, Shakhar Smorodinsky
theory similarity 0.61
Abstract · 21 pages

A set in $\mathbb{R}^d$ is $s$-convex if it is the union of at most $s$ convex sets. A family $F$ satisfies the $(p,q)$ property if among any $p$ sets in $F$, some $q$ intersect. Let $\mathrm{HD}_d^{(s)}(p,q)$ be the minimum number of points needed to pierce a finite family of $s$-convex sets that satisfies the $(p,q)$-property. Alon and Kalai (1995) proved that $\mathrm{HD}_d^{(s)}(p,q)$ exists for any $p \geq q \geq d+1$ and any $s \geq 1$, but the quantitative bounds they obtained are very loose. We present several improved upper and lower bounds, for a general $d$ and for $s$-intervals of the line (i.e., $\mathrm{HD}_1^{(s)}(p,q)$). In particular, we prove the following: (i) For every $d\ge2$, $s \geq 1$ and $δ>0$, if $p>q$ and $q\ge C_d\log(e sp)$, then $\mathrm{HD}_d^{(s)}(p,q) \le p-q+1 + O_{d,δ}((s \cdot \tfrac{p}{q} \cdot \log \tfrac{esp}{q})^{ρ_d+δ}),$ where $ρ_d<d$ is the exponent in the weak epsilon-net theorem of Rubin (2022). (ii) For $s \geq 1$, $p \geq q \geq 2$ and $q\ge C_0s\log(2s)\log(ep)$, $p-q+s \leq \mathrm{HD}_1^{(s)}(p,q) \leq p-q+2s+1$. This result provides the first near-tight estimate for $\mathrm{HD}_1^{(s)}(p,q)$ for $q>2$. (iii) For any fixed $s$, there are an integer $κ_s\in\{s,\ldots,2s\}$ and constants $C_s,p_s>0$ such that, whenever $p\ge p_s$ and $q\ge C_s\log(ep)$, $ \mathrm{HD}_1^{(s)}(p,q)\in\{p-q+κ_s,\;p-q+κ_s+1\}. $ Interestingly, this two-value concentration result holds, although the exact value of the threshold remains unknown. (iv) For any $s \geq 1$, $\mathrm{HD}_3^{(s)}(p,4) \geq sp^{2-o(1)}$. Already for families of convex sets, this significantly improves the best known lower bound on $\mathrm{HD}_d^{(1)}(p,d+1)$, for all $d \geq 3$.

0.38

Logarithmic asymptotics for polynomial threshold functions

cs.DM cs.ITmath.CO ·2026-10-25 ·Martin Anthony
theory similarity 0.60
Abstract · 39 pages. Revised exposition and organisation, with expanded explanations. Main results and theorem statements unchanged

We count Boolean functions represented as the sign of a real polynomial of bounded degree on the $n$-dimensional cube. We prove that the logarithm of their number is asymptotic to that of the classical hyperplane-arrangement upper bound, uniformly over all degrees, with relative error $O((\log n)^2/n)$. We also obtain sharper additive and relative error estimates in particular degree ranges, including an additive error $O(n^2)$ between the logarithms throughout a small linear degree range and improved bounds just below the central degree. The proof combines probabilistic estimates for Reed--Muller codes with a deletion argument for sets of evaluation vectors, an entropy count, and a sharp-threshold estimate for expected rank deficiency.

0.12

A Near-Linear Element-Kernel for \(d\)-Hitting Set

cs.DS cs.CC ·2026-09-06 ·Zimo Sheng, Mingyu Xiao
similarity 0.59
Abstract

In \(d\)-Hitting Set, the input consists of a finite universe \(U\), a family \(\mathcal S\) of subsets of \(U\) with size at most \(d\), and an integer \(k\). The task is to decide whether at most \(k\) elements of \(U\) can intersect every set in \(\mathcal S\). Previously known kernels contain \(O(k^{d-1})\) elements and \(O(k^d)\) sets. Whether the number of elements can be reduced to \(O(k^{d-1-\varepsilon})\) for some constant \(\varepsilon>0\) is a longstanding open problem in kernelization. In this paper, we answer this question affirmatively by giving a near-linear randomized element-kernel and a subquadratic deterministic element-kernel through a re-encoding of the instance. For every fixed \(d\geq3\), we give a one-sided randomized kernel with \(O_d(k\log^3k)\) elements and a deterministic kernel with \(O_d(k^{7/4}\log^{3/2}k)\) elements. Our kernels may still contain \(k^{O(d)}\) sets and the parameter \(k\) may grow polynomially.

0.21