LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

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

69 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

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.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 9 m
Compared with MathematicsShorter than 53%
Source channelInstitute for Advanced Study (YouTube)