Problem 37: Testing Submodularity

Proposed by	C. Seshadhri
Source	Bertinoro 2011
Short link	http://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.