Can submodularity be tested with polynomially many queries?

Submodular set functions capture diminishing returns, and many algorithms take one as a black box. How many evaluations does it take to check that a black box is submodular, or far from it? The best known tester needs a number of queries exponential in about $\sqrt n$, while the best lower bound is about $n^2$.

Problem

Identify $\{0,1\}^n$ with the subsets of $[n]$. A function $f : \{0,1\}^n \to \mathbb{R}$ is submodular if for all $S \subseteq T \subseteq [n]$ and every $i \notin T$,

$$f(T \cup \{i\}) - f(T) \le f(S \cup \{i\}) - f(S).$$

The distance of $f$ from submodularity is the smallest fraction of the $2^n$ points at which $f$ must be changed to make it submodular, and $f$ is $\varepsilon$-far if this distance is at least $\varepsilon$. A tester queries values of $f$, accepts every submodular $f$ with probability at least $2/3$ and rejects every $\varepsilon$-far $f$ with probability at least $2/3$.

Question. How many queries are needed? In particular, is there a tester making $\mathrm{poly}(n, 1/\varepsilon)$ queries?

The source also singles out special cases: testing whether $f$ is the rank function of a matroid (monotone, submodular, with every marginal $f(S \cup \{i\}) - f(S)$ equal to 0 or 1), and testing coverage functions, $f(S) = \mu\big(\bigcup_{i \in S} V_i\big)$ for sets $V_i$ in a measure space, a case suggested by Noam Nisan.

Background

Submodular functions are central in combinatorial optimization and in algorithmic game theory, where they model valuations, and most algorithms for them assume oracle access. Seshadhri and Vondrák started the study of testing submodularity on the hypercube with Hamming distance [1]; Parnas, Ron and Rubinfeld had earlier treated the special case of Monge matrices [3]. C. Seshadhri posed the question at the 2011 Bertinoro Workshop on Sublinear Algorithms. For functions with values in $\{0,1\}$ the problem is easy; already for a constant-size range it is open.

What is known

• Upper bound. A natural tester that samples local violations uses $(1/\varepsilon)^{O(\sqrt n \log n)}$ queries (Seshadhri and Vondrák) [1].
• Lower bounds. Seshadhri and Vondrák proved a linear lower bound and examples suggesting the natural tester cannot be efficient in $\varepsilon$ [1]. Hatami and Vondrák raised the bound to $\Omega(n^2/\log n)$ queries for constant $\varepsilon \le 1/4$, which also separates submodularity from modularity [2].
• Other distances. With $\ell_p$ distance instead of Hamming distance, submodularity of functions into $[0,1]$ can be tested with a constant number of queries (Blais and Bommireddi, 2017) [4].
• Still open in 2026. A 2026 study of $k$-submodular functions describes the exponential gap for ordinary submodularity as unresolved [5].

What would count as progress

• A tester with $\mathrm{poly}(n, 1/\varepsilon)$ queries and a proof, or even $2^{o(\sqrt n)}$ queries for constant $\varepsilon$.
• A lower bound of $n^{\omega(1)}$ queries, for example a distribution of functions far from submodular whose violations are spread too thin to be found. For small $n$ the exact distance of a candidate function from submodularity can be computed by integer programming.
• Either of the above for matroid rank functions or coverage functions.

References

1. C. Seshadhri and J. Vondrák, Is submodularity testable?, Algorithmica 69(1) (2014), 1–25 (ICS 2011). doi:10.1007/s00453-012-9719-2
2. P. Hatami and J. Vondrák, Testing real-valued modularity and submodularity, manuscript, 2016. PDF
3. M. Parnas, D. Ron and R. Rubinfeld, On testing convexity and submodularity, SIAM J. Comput. 32(5) (2003), 1158–1184. doi:10.1137/S0097539702414026
4. E. Blais and A. Bommireddi, Testing submodularity and other properties of valuation functions, ITCS 2017, LIPIcs 67, 33. doi:10.4230/LIPIcs.ITCS.2017.33
5. T. Haris and D. Palit, Testing $k$-submodularity, 2026. arXiv:2606.30433

Source

Imported from Sublinear.info, Problem 37, curated by Sublinear.info editors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.