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

We prove nearly quadratic (in the dimension) lower bounds for randomized algorithms for two basic problems: linear optimization and uniform sampling over convex bodies in the membership oracle model (a convex body K is specified by a point in K, the radii of two balls that sandwich K, and an oracle that takes any query point x and determines whether x is in K). For linear optimization, the lower bound matches the known nearly quadratic upper bound (up to a polylog factor in the dimension) and has further interesting consequences. Our construction, which is a distribution over parallelopipeds, also yields the same lower bound for randomized volume estimation.