# Problem 37: Testing Submodularity

From Open Problems in Sublinear Algorithms

Suggested by | C. Seshadhri |
---|---|

Source | Bertinoro 2011 |

Short link | https://sublinear.info/37 |

A function $f:\{0,1\}^n \mapsto R$ is *submodular* if for every $i \in
[n]$ and every $S \subset T$, such that $i \notin T$,
\[f(T \cup
\{i\})-f(T) \leq f(S \cup
\{i\})-f(S) \ .\]

**Question:** How efficient can we test that $f$ is submodular (in
terms of number of queries to $f$). In particular, can one do it in $\operatorname{poly}(n/\epsilon)$?
Special cases of interest that are open:

- $f$ is monotone and for every $S$ and $i \in [n]$, $f(S \cup \{i\})-f(S)$ is either 0 or 1. In this case $f$ is the rank function of a matroid.
- A more special case (suggested by Noam Nisan): $f$ is said to be a
*coverage valuation*if every $i \in [n]$ is associated with a set $V_i$ from some measurable space with a measure $\mu$ (we might want to think of $V_i$ as discrete, in which case the measure is just the cardinality). Then $f$ is defined by $f(S) = \mu(\bigcup_{i \in S} V_i)$. Observe that such $f$ is a submodular function.

**Background:** The problem is interesting in algorithmic game theory.
The best known upper bound on the number of queries is
$O({\epsilon^{-\sqrt{n}\log n}})$ [SeshadhriV-11]. We do not know the answer even for constant size $R$, although for $R = \{0,1\}$ it is easy.