← 研踪 PaperTrailarXiv:2611.02374 · v1
Submodularity Is Barely Testable
首次提交 2026-11-02 09:39
版本更新 2026-11-02 09:39
雷达观测 2026-11-04 23:42
摘要
In 2010, Seshadhri and Vondrák asked: is submodularity testable? For functions $f : \{ 0, 1 \}^n \to \mathbb{R}$, they gave a tester that makes $2^{O(\sqrt{n} \log n)}$ queries. We show that every tester, even an adaptive one with two-sided error, must make $2^{Ω(\sqrt{n})}$ queries, thereby concluding: submodularity is barely testable.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-02 09:39 · 最新观测版本
Submodularity Is Barely Testable
In 2010, Seshadhri and Vondrák asked: is submodularity testable? For functions $f : \{ 0, 1 \}^n \to \mathbb{R}$, they gave a tester that makes $2^{O(\sqrt{n} \log n)}$ queries. We show that every tester, even an adaptive one with two-sided error, must make $2^{Ω(\sqrt{n})}$ queries, thereby concluding: submodularity is barely testable.
查看此版本解读 →查看此版本原文 ↗