Open Problems:37 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:53:32Z

updated header

Krzysztof Onak at 05:29, 16 November 2012

2012-11-16T05:29:48Z

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 37: Testing Submodularity}} {{Infobox |label1 = Proposed by |data1 = C. Seshadhri |label2 = Source |data2 = Bertinoro 2011 ..."

2012-11-13T15:21:50Z

Created page with "{{DISPLAYTITLE:Problem 37: Testing Submodularity}} {{Infobox |label1 = Proposed by |data1 = C. Seshadhri |label2 = Source |data2 = Bertinoro 2011 ..."

New page

{{DISPLAYTITLE:Problem 37: Testing Submodularity}}
{{Infobox
|label1 = Proposed by
|data1 = C. Seshadhri
|label2 = Source
|data2 = [[Workshops:Bertinoro_2011|Bertinoro 2011]]
|label3 = Short link
|data3 = 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}})$ {{cite|SeshadhriV-11}}. We do not know the answer even for constant size $R$, although for $R = \{0,1\}$ it is easy.

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro11
 |who=C. Seshadhri

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 37: Testing Submodularity}}
+{{Header
-{{Infobox
+|title=Testing Submodularity
-|label1 = Proposed by
+|source=bertinoro11
-|data1 = C. Seshadhri
+|who=C. Seshadhri
 }}
 A function $f:\{0,1\}^n \mapsto R$ is ''submodular'' if for every $i \in