Talks
Fall 2021

Lower Bounds for Sampling: Dimension Two and Gaussians

Tuesday, January 10th, 2023, 2:45 pm3:30 pm

Add to Calendar

Speaker: 
Location: 

Calvin Lab Auditorium

Query lower bounds for log-concave sampling remain scarce, but this talk will cover some recent progress for two cases. First, in dimension d >= 2, the lower bound for log-concave sampling is log κ, where κ is the condition number; this is tight in any fixed dimension. Second, the lower bound for sampling from Gaussians is min(d, κ^{1/2}), which is nearly tight (up to a log factor). This is based on joint with with Jaume de Dios Pont, Jerry Li, Chen Lu, and Shyam Narayanan.