Talks
Fall 2021
Lower Bounds for Sampling: Dimension Two and Gaussians
Tuesday, January 10th, 2023, 2:45 pm–3:30 pm
Speaker:
Sinho Chewi (MIT)
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.