A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
arXiv:2609.30215v1 Announce Type: cross Abstract: We prove nearly quadratic lower bounds for randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership ora