论文给出并行扩散采样的轮数下界

Yiwen Kou 与 Yimeng Wang 的论文为并行扩散采样建立了首批多项式轮数下界。在每轮允许多项式次查询、分数函数满足均方误差保证的条件下，论文证明平滑近各向同性高斯混合采样至少需要约 d^(1/3) 轮，而从单位球内各向异性轴对齐盒子均匀采样需要 Ω(d) 轮，且该界是紧的。这些结论适用于每轮在任意位置和噪声水平做多项式次查询的任意随机算法。