Recognizing Coverage Functions

Abstract

A coverage function $f$ over a ground set $[m]$ is associated with a universe $U$ of weighted elements and $m$ sets $A_1,ldots,A_m subseteq U$, and for any $Tsubseteq [m]$, $f(T)$ is defined as the total weight of the elements in the union $cup_{jin T} A_j$. Coverage functions are an important special case of submodular functions, and arise in many applications, for instance, as a class of utility functions of agents in combinatorial auctions. Naïve representations of coverage functions have size exponential in $m$, and in algorithmic applications, an access to a value oracle is assumed. In this paper, we ask whether one can recognize if a given oracle is that of a coverage function or not. We demonstrate an algorithm which makes $O(m|U|)$ queries to an oracle of a coverage function and completely reconstructs it. This is polynomial time whenever $|U|$ is polynomially bounded implying the function has a succinct description. To complement the above result, we show a negative result. We prove that “noncoverageness” needs large certificates---there exists a function which is not coverage and yet any algorithm making fewer than $2^{m-1}$ queries cannot distinguish this function from some coverage function. Our positive result shows that the property of coverageness has $O(m|U|)$-query proximity oblivious testers, while our negative result shows an exponential lower bound. We believe our lower bound also goes through for general property testers, and provide some evidence of the same.