Reproduce “A Linear Lower Bound for Convex Body Chasing in Every Norm” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Nicolas Christianson

The authors prove that convex body chasing has a worst-case competitive ratio at least linear in dimension, for every norm. They encode a recursive two-branch dilemma as convex requests. For every dimension d≥2, some request sequence forces ratio at least c d, matching the O(d) upper bound up to constants; the lower bound applies to general, not nested, requests.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.