A Linear Lower Bound for Convex Body Chasing in Every $\ell_p$ Norm
We establish an $Ω(d)$ lower bound on the competitive ratio of convex body chasing in $\mathbb{R}^d$ with $\ell_p$ movement costs for any $p \in [1, \infty)$. Previously, the best known lower bound for general $p$ was $Ω(\max\{\sqrt{d}, d^{1-1/p}\})$, established by Bubeck et al. (2019); a linear lower bound was known only for $p = \infty$, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior bound for every fixed $p \in [1, \infty)$ and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.32670
curl -X POST /api/v1/records/arxiv/2610.32670/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.32670/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'