09:40
官方一手arXiv: OpenAI@Barna Saha, Yinzhan Xu, Christopher Ye
精选
推荐理由：这篇论文把SETH下界从特殊维度扩展到所有可构造维度，说明计算几何经典问题的维度依赖几乎无法消除。
SETH
共 1 条相关 AI 资讯
6月25日
09:40
该论文证明在SETH假设下，Furthest Pair、Bichromatic Closest Pair等几何问题在d=ω(1)维度时需n^{2-o(1)}时间。此前Chen (2020)只对d=2^{Θ(log^* n)}维度成立。新结果将所有可构造维度纳入下界，意味着现有f(d)·n^{2-Θ(1/d)}算法的维度依赖本质上不可避免。证明技术利用了OpenAI近期对Erdos单位距离猜想的反证方法。