
A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
Santosh Vempala of Georgia Tech presents a lower bound result in computational geometry, delivered as part of the IAS Computer Science/Discrete Mathematics Seminar. He proves that randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership oracle model require nearly quadratic query complexity in the dimension, matching known upper bounds up to a polylogarithmic factor. The convex body is specified by an interior point, two sandwiching ball radii, and a membership oracle that answers whether a query point lies inside it. Vempala walks through the construction, a distribution over parallelepipeds, showing how the same technique also yields a matching lower bound for randomized volume estimation. The talk is aimed at a specialist audience in theoretical computer science and discrete mathematics, working through the proof technique and its consequences for optimization, sampling, and volume computation over convex sets.