A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model

Summary

The paper proves nearly quadratic lower bounds Ω(n²/log⁹n) on the expected number of membership queries required by randomized algorithms for three classical problems over convex bodies in Rⁿ: approximate linear optimization, uniform sampling (to total variation distance 1/10), and factor-2 volume estimation. The hard instances are random centrally symmetric parallelepipeds K_j(R) cut out by n independent Gaussian constraint rows; the two bodies differ only in the bound along the last row (length L versus 3L), so any distinguishing algorithm must find a 'separating' query in K₂\K₁. The core contribution is a product-partition theorem (Theorem 1.5): any disjoint family of convex product parts with total Gaussian measure at least η, each localizing the normal of the first n−1 rows to a fixed radius, contains a subfamily of measure at least η/2 whose parts each have measure at most exp(−a·n²/log⁸n). The proof chains three steps — localization forces determinant-sign stability, sign stability forces large relative entropy via a dimension-reduction induction with a Gaussian Brascamp–Lieb bound, and entropy forces small part measure. Consequences include optimality, up to polylog factors, of reductions among the five Grötschel–Lovász–Schrijver oracles and a classical-versus-quantum query separation. Main limitations: a log⁹ gap to the nearly quadratic upper bound of Lee–Sidford–Vempala, and hardness restricted to parallelepiped-type instances.