We show that for any constants $epsilon > 0$ and $p ge 1$, given oracle access to an unknown function $f : {0,1}^n o [0,1]$ it is possible to determine if the function is submodular or is $epsilon$-far from every submodular function, in $ell_p$ distance, with a emph{constant} number of queries to the oracle. We refer to the process of determining if an unknown function has a property, or is far from every function having the property, as emph{property testing}, and we refer to the algorithm that does that as a tester or a testing algorithm. A function $f : {0,1}^n o [0,1]$ is a emph{$k$-junta} if there is a set $J subseteq [n]$ of cardinality $|J| le k$ such that the value of $f$ on any input $x$ is completely determined by the values $x_i$ for $i in J$. For any constant $epsilon > 0$ and a set of $k$-juntas $mathcal{F}$, we give an algorithm which determines if an unknown function $f : {0,1}^n o [0,1]$ is $frac{epsilon}{10^6}$-close to some function in $mathcal{F}$ or is $epsilon$-far from every function in $mathcal{F}$, in $ell_2$ distance, with a constant number of queries to the unknown function. This result, combined with a recent junta theorem of Feldman and Vondrak (2016) in which they show every submodular function is $epsilon$-close, in $ell_2$ distance, to another submodular function which is a $ilde{O}(frac{1}{epsilon^2})$-junta, yields the constant-query testing algorithm for submodular functions.We also give constant-query testing algorithms for a variety of other natural properties of valuation functions, including fractionally additive (XOS) functions, OXS functions, unit demand functions, coverage functions, and self-bounding functions.
PDF
download
878987797
028-85220240
