Name
Abstract | ||
|---|---|---|
We prove that any submodular function f: {0, 1}n → {0, 1,..., k} can be represented as a pseudo-Boolean 2k-DNF formula. Pseudo-Boolean DNFs are a natural generalization of DNF representation for functions with integer range. Each term in such a formula has an associated integral constant. We show that an analog of Håstad's switching lemma holds for pseudo-Boolean k-DNFs if all constants associated with the terms of the formula are bounded. This allows us to generalize Mansour's PAC-learning algorithm for k-DNFs to pseudo-Boolean k-DNFs, and hence gives a PAC-learning algorithm with membership queries under the uniform distribution for submodular functions of the form f: {0, 1}n → {0, 1,..., k}. Our algorithm runs in time polynomial in n, @@@@ and log(1/δ) and works even in the agnostic setting. The line of previous work on learning submodular functions [Balcan, Harvey (STOC '11), Gupta, Hardt, Roth, Ullman (STOC '11), Cheraghchi, Klivans, Kothari, Lee (SODA '12)] implies only nO(k) query complexity for learning submodular functions in this setting, for fixed ε and δ. Our learning algorithm implies a property tester for submodularity of functions f: {0, 1}n → {0,..., k} with query complexity polynomial in n for k = O((log n/log log n)1/2) and constant proximity parameter ε. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.5555/2627817.2627915 | SODA |
Keywords | DocType | Volume |
algorithms,design,algebraic algorithms,general,theory | Journal | abs/1208.2294 |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 9 | 0.50 |
References | Authors | |
18 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sofya Raskhodnikova | 1 | 991 | 64.59 |
| Grigory Yaroslavtsev | 2 | 209 | 17.36 |