Computer Science/Discrete Mathematics Seminar I

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.