CS Paper Radar

Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions

Yegor Gorodzha, Steven Hoehner, Gil Kur

cs.CG math.MGcs.LGmath.PR ·submitted 2026-10-26 00:29 UTC · v2
theory

Abstract

We provide sharp estimates on the number of vertices needed to approximate the Euclidean unit ball $B_d\subset\mathbb R^d$ with relative symmetric-difference volume error at most $\varepsilon\in(0,1)$. We show that the minimum vertex budget $N_\varepsilon(d)$ satisfies $$\log N_\varepsilon(d)\asymp d\log\left(1+\frac1{\varepsilon\sqrt d}\right).$$ In particular, $\exp(O(\sqrt d/\varepsilon))$ vertices suffice for every $\varepsilon\in(0,1)$ and all sufficiently large $d$. We also prove that achieving a fixed error $\varepsilon\in(0,1)$ requires at least $Ω\bigl((\tfrac{1+\varepsilon}{2\sqrt\varepsilon})^{d-1}\bigr)$ facets, an exponential number in $d$. We extend our vertex approximation result to Gaussian symmetric-difference error, and give a positive answer to the question of De, Nadimpalli, and Servedio about subexponential vertex complexity for approximating Euclidean balls. We also disprove a Macbeath-type extremality principle for unrestricted vertex approximation. Whereas the ball uniformly maximizes the inscribed approximation error among all convex bodies (Macbeath, 1951), we show that approximating the hypercube $[-1,1]^d$ to relative error $\varepsilon$, with $δ:=1-\varepsilon$, requires $N\ge\fracδ{2}\exp(Ω(δ^2d/\log^2(2/δ)))$ vertices whenever $d\ge16\log(2/δ)$. Thus, when $d$ is large, the cube is harder to approximate than the ball in this sense. Finally, we determine the sharp dimensional order of the classical Laguerre-Delone triangulation number, showing that $\mathrm{ldel}_{d-1}=Θ(d^{-1/2})$ as $d\to\infty$. This improves both the upper bound of Ludwig, Schütt, and Werner and the lower bound of Böröczky by a factor of order $\sqrt d$. By classical asymptotic approximation theorems (Ludwig, 1999), this improvement applies to every convex body in $\mathbb R^d$ with $C^2$ boundary and positive Gaussian curvature.

Comment
71 pages, 1 figure, 1 table. v2: exposition and references revised for a broader audience

Closest papers

Nearest neighbours by meaning across the whole index.

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.67
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

Strong Lower Bounds for Weak Epsilon-Nets

cs.CG ·2026-10-29 ·Sujoy Bhore, Reilly Browne, Da Wei Zheng
theory similarity 0.64
Abstract

Let $P$ be a finite point set in $\mathbb{R}^d$. A weak $\varepsilon$-net for $P$ with respect to convex sets is a finite set $X\subset\mathbb{R}^d$ intersecting every convex set containing at least $\varepsilon|P|$ points of $P$. Determining their optimal worst-case size was described by Alon, Kalai, Matousek, and Meshulam [Adv. Appl. Math., 2002] as "one of the truly important open problems in combinatorial geometry." We give elementary constructions which establish the first polynomially superlinear lower bounds in fixed dimension. Already in $\mathbb{R}^3$, we construct point sets for which every weak $\varepsilon$-net has size $Ω(\varepsilon^{-3/2})$. More generally, for every fixed $d\ge3$, we obtain a lower bound of $Ω_d(\varepsilon^{-γ_d})$, where $γ_d=\sqrt{d/2}+O(1)$. Consequently, no upper bound of the form $O_d(\varepsilon^{-C})$ can hold with an absolute constant $C$ which is independent of the dimension. Despite the recent progress on upper bounds, the strongest previous general lower bound remained $Ω_d(\varepsilon^{-1}\log^{d-1}(1/\varepsilon))$, due to Bukh, Matousek, and Nivasch [Israel J. Math., 2011]. To obtain our results, we apply a quadratic lift to grid-based configurations with many point-line incidences. The bounds also yield polynomial separations between fractional and integral piercing numbers of convex families, and lower bounds for Hadwiger-Debrunner numbers.

0.25

On Complexity of Gaussian Sampling

cs.CC stat.CO ·2026-10-14 ·Huanjian Zhou, Taiji Suzuki
theory similarity 0.61
Abstract · 36 pages

We study the number of exact matrix-vector queries needed to sample a centered $d$-dimensional Gaussian with condition number at most $κ$ to total variation error $\varepsilon$. The best known algorithm uses $O(\min\{d,\sqrtκ\log(\frac{d}{\varepsilon})\})$ queries, while the known lower bounds do not grow as $\varepsilon\to0$ and match this bound only for $κ\le d^{1/5-δ}$ at constant accuracy. We introduce a construction based on a hidden determinant sign and prove a lower bound of $Ω\!\left(\min\left\{d,\sqrtκ\log\left(1+\frac{d}{\sqrtκ\,\varepsilon}\right)\right\}\right)$ uniformly for all $d\ge1$, $κ\ge4$, and $0<\varepsilon\le\tfrac{1}{16}$. This bound matches the known upper bound up to constant factors whenever $κ\le d^{2-δ}$ for fixed $δ\in(0,2)$, or $\varepsilon\le d^{-c}$ for fixed $c>0$. We also extend a recent fixed-spectrum construction with a hidden eigenbasis from $κ=2$ to $2\leκ\le d^{1-δ}$, for any fixed $δ\in(0,1)$. This gives an $Ω_δ(\sqrtκ\log d)$ lower bound at constant accuracy that holds even when the spectrum of the precision matrix is known to the algorithm.

0.13

A Linear Lower Bound for Convex Body Chasing in Every Norm

cs.DS cs.CGmath.MG ·2026-10-23 ·Nicolas Christianson
theory similarity 0.61
Abstract · Updates the previous version to extend the lower bound to all norms

We establish an $Ω(d)$ lower bound on the competitive ratio of convex body chasing in $\mathbb{R}^d$ with movement costs measured in any norm. Previously, the best known lower bound valid across all norms was $Ω(d^{1/6})$, established by Papazov (2023); stronger lower bounds were known for $\ell_p$ norms, where Bubeck, Klartag, Lee, Li, and Sellke (2019) had established a lower bound of $Ω(\max\{\sqrt{d}, d^{1-1/p}\})$. In particular, a linear lower bound was known only for the $\ell_\infty$ norm, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior universal and $\ell_p$ lower bounds for $p < \infty$ and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio $O(d)$ - is asymptotically optimal for every norm. Our approach is based on the recursive construction of Bubeck, Coester, and Rabani (2023) for metrical service systems, which gives a lower bound of $Ω(r^2)$ for requests of size $O(r)$. We show that requests in their construction, each comprising a set of discrete points in a graph metric, can be mapped to the vertices of convex requests in a $(2r+1)$-dimensional $\ell_p$ vector space while approximately preserving movement costs up to a factor of $O(r)$; the general result then follows via Milman's (1985) quotient-of-a-subspace theorem.

0.29

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

Bounded Relative Boundary Implies Narrow DNF Approximation

cs.CC cs.DM ·2026-08-31 ·Chenghua Liu, Boning Meng
theory similarity 0.61
Abstract · 13 pages; proof and exposition revised, Lean repository linked

We prove Friedgut's conjecture (J. Amer. Math. Soc. 12 (1999)) that every increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have size bounded independently of the dimension and the bias. For $0<p\le 1/2$, every increasing Boolean function with total resampling influence at most $K$ is $\varepsilon$-close under $μ_p^n$ to a monotone DNF of width $\exp(O((K+1)^2/\varepsilon^2))$, from which the full conjecture follows for all $p\in(0,1)$. We build on Hatami's pseudo-junta theorem (Ann. of Math. 176 (2012)), whose approximator need not be increasing. Our randomized shifts produce an increasing approximator that is measurable with respect to a controlled refinement of Hatami's adaptive partition. Retaining only short positive certificates yields the desired narrow DNF.

0.35

Resolving Tusnády's Problem

cs.CG math.CAcs.DSmath.CO ·2026-11-04 ·Nicola Wengiel
theory similarity 0.61
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

Sharp Lower Bounds for Parallel Log-Concave Sampling

cs.DS math.PR ·2026-11-11 ·Evan Dogariu
theory similarity 0.60
Abstract

How many rounds of parallel queries are needed to sample from a smooth, strongly log-concave distribution on $\mathbb{R}^d$? For every fixed condition number $κ\in (1, \infty)$, we prove that any sampler making polynomially many queries per round requires $Ω_κ(\log d)$ rounds to achieve constant total variation error in the worst case. The lower bound holds even if queries return derivatives of all orders. Together with the first-order parallel Picard algorithm of \cite{zhou2025parallel}, this establishes a depth complexity of $Θ_κ(\log d)$ for parallel log-concave sampling with $\operatorname{poly}(d)$ width. We then study centered Gaussian targets to understand how much width is needed at a given depth. From \cite{chewi2023query,zhou2026complexitygaussiansampling}, it is known that either one round of width $d$ or $\mathcal{O}(\sqrtκ \log d)$ rounds of constant width suffice for first-order Gaussian sampling. At fixed $κ$ we characterize the depth-width tradeoff interpolating between these regimes: when using $ \lceil c \log d\rceil$ rounds, if $0 < c < c_\star(κ)$ then the optimal width at constant TV error is $\widetildeΘ(d^{1-c/c_\star(κ)})$, while if $c \geq c_\star(κ)$ then it is $Θ_κ(1)$. Here, $c_\star(κ)$ is an explicit constant with $c_\star(κ) \sim \sqrtκ / 8$ as $κ\to \infty$.

0.05