Optimal Zonotope Containment via Adaptive Gaussian Sampling
Abstract
We investigate the convex-body containment problem max{s >0 : s Z ⊆ Q}, where the outer body Q ⊆ ℝd is described by a membership oracle and the inner body Z ⊆ ℝd is a zonotope. Our main result is a sampling-based O(√(d/log d))-approximation algorithm for this problem that matches the lower bound of Ω(√(d/log d)) by Khot and Naor in the oracle model. Starting from approximate Lewis position, the algorithm samples Gaussian directions and adaptively shortens and repositions the generators. Its analysis combines preservation of the support in a fixed direction with contraction of the corresponding functional after renormalization. Crucially, the algorithm works directly with the input generators and does not use zonotope sparsification. We complement this result with a \emph{universal} Ω(√(d/log d)) lower bound holding for \emph{all} full-dimensional zonotopes when the number of oracle queries is polynomial in d. Finally, we consider containment problems max{s >0 : s K ⊆ Q}, for general convex bodies K ⊆ ℝd. A result of Nasz{ó}di on approximating K ⊆ ℝd by a polytope implies a Θ(d/log d) approximation algorithm in polynomial time when the centroid of K is the origin. We show the tightness of this approximation factor in the oracle model via a reduction to the circumradius computation. Our lower bound holds for centrally symmetric convex sets, implying that Barvinok's optimal O(√d)-approximation of a centrally symmetric convex body by a polytope with a polynomial number of vertices cannot be computed in polynomial time.
Related
- Optimal Slice-Adaptive Tuning of Hybrid Slice Sampling
- Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence
- Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start
- Log-depth entanglement transition in hypercube Gaussian boson sampling
- Anticoncentration and entanglement in Gaussian boson sampling
BibTeX
@misc{eisenbrand2026optimal,
title = {{Optimal Zonotope Containment via Adaptive Gaussian Sampling}},
author = {Friedrich Eisenbrand and Thomas Rothvoss and Matteo Russo and Ruben Skorupinski},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2605.04183},
eprint = {2605.04183},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.04183},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Zonotope Containment via Adaptive Gaussian Sampling
AU - Friedrich Eisenbrand
AU - Thomas Rothvoss
AU - Matteo Russo
AU - Ruben Skorupinski
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2605.04183
UR - https://arxiv.org/abs/2605.04183
AB - We investigate the convex-body containment problem max{s >0 : s Z ⊆ Q}, where the outer body Q ⊆ ℝ^d is described by a membership oracle and the inner body Z ⊆ ℝ^d is a zonotope. Our main result is a sampling-based O(√(d/log d))-approximation algorithm for this problem that matches the lower bound of Ω(√(d/log d)) by Khot and Naor in the oracle model. Starting from approximate Lewis position, the algorithm samples Gaussian directions and adaptively shortens and repositions the generators. Its analysis combines preservation of the support in a fixed direction with contraction of the corresponding functional after renormalization. Crucially, the algorithm works directly with the input generators and does not use zonotope sparsification. We complement this result with a \emph{universal} Ω(√(d/log d)) lower bound holding for \emph{all} full-dimensional zonotopes when the number of oracle queries is polynomial in d. Finally, we consider containment problems max{s >0 : s K ⊆ Q}, for general convex bodies K ⊆ ℝ^d. A result of Nasz{ó}di on approximating K ⊆ ℝ^d by a polytope implies a Θ(d/log d) approximation algorithm in polynomial time when the centroid of K is the origin. We show the tightness of this approximation factor in the oracle model via a reduction to the circumradius computation. Our lower bound holds for centrally symmetric convex sets, implying that Barvinok's optimal O(√d)-approximation of a centrally symmetric convex body by a polytope with a polynomial number of vertices cannot be computed in polynomial time.
ER -