An explicit linear competitive-ratio lower bound in finite-dimensional
ProvedConvexBodyChasing.competitive_ratio_linear_lower_boundcbc-local-formalizationconvex-body-chasingnormed-spaces
Let be a natural number and let . Consider a randomized online algorithm for nonempty compact convex requests in , starting at the origin. Randomness is represented by a probability space of seeds with measurable decisions. If satisfies the competitive guarantee against every feasible comparator path, then
The constant is absolute and independent of , the dimension, and the algorithm. This is the competitive-ratio consequence of the recursive request construction and Proposition 9, with explicit nonoptimized constants and dimension padding. It supplies the Euclidean lower bound used in the quotient-of-a-subspace reduction to an arbitrary norm.
Preamble
import Definitions.Def_CBCCompactChasingModel open scoped ENNReal open ConvexBodyChasing
Formal statement
theorem ConvexBodyChasing.competitive_ratio_linear_lower_bound (d : ℕ) (hd : 3 ≤ d)
(p : ℝ≥0∞) [Fact (1 ≤ p)] (hp : p ≠ ∞)
(A : RandomizedOnlineAlgorithm (Space d p)) (R : ℝ)
(hcomp : RandomizedCompetitive A 0 R) : (d : ℝ) / 128000000 ≤ R := by sorry
Source
Nicolas Christianson, A Linear Lower Bound for Convex Body Chasing in Every Norm, STOC 2027 submission #674, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/674.pdf, Proposition 9, p. 14, and its competitive-ratio consequence on p. 15; explicit constant and dimension padding from the accompanying local Lean formalization.