概念
信息论下界
刻画在无计算资源限制、仅受数据量约束时任何算法（甚至指数时间）能达到的最优表现的理论下界。
时间轴 (近 90 天)
10月19日
论文的误差阶与信息论下界在 s 和 D 的依赖关系上一致，仅相差常数和 log N 因子。
待验证50%
10月15日
信息论下界刻画的是在无计算资源限制下任何算法（甚至指数时间）能达到的最优表现，本问题中对应Õ(md+k)；计算下界则假设算法必须在多项式时间内运行，得到的下界通常更大。
待验证50%
10月7日
作者提供了新的信息论下界，从极小极大意义上证明误差对q的复杂依赖关系是根本性的，而非算法设计的人为产物
待验证50%