本文在成员查询模型（membership oracle）中证明了线性优化和均匀采样的随机算法的准二次下界。设 $K\subset\mathbb{R}^n$ 为凸体，成员查询能够判断任意点 $x$ 是否属于 $K$。线性优化问题为 $$\max_{x\in K} c^{\top}x,$$ 其中 $c\in\mathbb{R}^n$ 为给定方向向量。
作者构造了一族参数化的凸体，使得任意算法在 $\tilde{\Omega}(n^2)$ 次查询后才能区分不同实例，从而得到 $$T_{\text{opt}}(n)=\tilde{\Omega}(n^2)$$ 的下界。这里的 $\tilde{\Omega}$ 隐含了 $\operatorname{polylog}(n)$ 因子。该下界恰好匹配已知的上界 $\tilde{O}(n^2)$（如基于椭圆法或随机游走的算法），说明在该模型下二次复杂度是不可避免的。
对于均匀采样，即从 $K$ 中抽取近似均匀分布的样本，作者进一步证明了 $$T_{\text{sample}}(n)=\tilde{\Omega}(n^2),$$ 这比之前仅 $\Omega(n)$ 的已知下界提升了一个数量级。由于体积估计可以归约为均匀采样，同样得到 $\tilde{\Omega}(n^2)$ 的体积下界。
证明的核心思路是将已知的隐藏超平面（hidden hyperplane）问题嵌入到凸体的构造中，使得不同实例在少于 $\tilde{\Omega}(n^2)$ 次查询下几乎不可区分。通过信息论的熵下界，得到所需的查询次数。
技术要点
- 成员查询模型只能返回“在/不在”，不提供梯度或距离信息。
- 构造的凸体族在局部几何上高度相似，仅在细微的方向上有差异。
- 使用随机化的对抗性实例，使得任何算法必须对所有方向进行近似探索。
该工作表明，在仅依赖成员查询的设置下，线性优化、均匀采样以及体积估计的复杂度本质上受限于 $n^2$ 级别的查询开销。
点评