A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies
Examine the computational complexity of linear optimization over convex bodies, presenting nearly quadratic lower bounds for randomized algorithms in the membership oracle model.
