09:40
arXiv: OpenAI@Barna Saha, Yinzhan Xu, Christopher Ye
精选
推荐理由：这篇论文把SETH下界从特殊维度扩展到所有可构造维度，说明计算几何经典问题的维度依赖几乎无法消除。
精选
过去 24 小时，从 655 条中筛出 45 条
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单位距离猜想的反证方法。
6月11日
15:28
AITOP6月11日 15:28
15:23
AITOP6月11日 15:23
15:07
AITOP6月11日 15:07
6月1日
00:09
AITOP6月1日 00:09
