Submodularity functions require many queries to test accurately
Submodularity Is Barely Testable
Data Structures and Algorithms
Summary
Testing whether a function has a property called submodularity is important in optimization and computer science. The authors show that any method to check this property has to make a very large number of queries, growing exponentially with the square root of the input size. This means testing submodularity is much harder than some other properties and cannot be done quickly or with limited information. Their result sets a near-limit on how efficiently submodularity can be tested.
What this means in practice
- •For algorithm designers: Avoid relying on quick tests of submodularity when designing optimization algorithms over large inputs, due to inherent high query cost.
- •For complexity theorists: Use the established lower bound on submodularity testing queries to inform study of related function properties and testing limits.
A theory result. No direct application yet.
Authors
Diptaksho Palit, Yuichi Yoshida
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.