Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities

We study the query complexity of sampling from smooth distributions on Rᵈ using first-order oracles. For d-dimensional strongly log-concave targets with condition number $κ=2$, we prove that any randomized sampler requires exp(Ω(log1/3 d)) queries even from a constant warm start. This rules out polylogarithmic dimension dependence and strictly separates strongly log-concave sampling from Gaussian sampling. For targets with L-smooth potentials satisfying an $α$-log-Sobolev inequality with $κ= L/α$, we prove an $Ω(κ)$ query lower bound for dlog²κ. This shows that log-Sobolev sampling is strictly harder than strongly log-concave sampling. Our proofs construct instance-dependent tests that target samples typically pass but outputs of algorithms making few queries typically fail. For strongly log-concave targets, we embed a sequence of hidden Gaussian into high-degree tensor polynomial with smooth gates, forcing any algorithm to uncover the layers sequentially. The log-Sobolev construction hides a constant fraction of the target mass in angular caps while controlling the log-Sobolev constant via delicate estimates.