arXiv preprint ·
Submodularity Is Barely Testable
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Efficient Proper Agnostic Learning of Halfspaces
A Constant-Factor Approximation for Capacitated Facility Location with Outliers
Semidirect sums of tensors and the matrix multiplication exponent
Generalized Flows over Time: Complexity, Structure and Algorithm
Incremental Open Addressing Has No Time-Space Tradeoff
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.