{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:21:38Z","timestamp":1787322098055,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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 $T\\subseteq [m]$, $f(T)$ is defined as the total weight of the elements in the union $\\cup_{j\\in 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\u00efve 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 \u201cnoncoverageness\u201d 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.<\/jats:p>","DOI":"10.1137\/140964072","type":"journal-article","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T12:23:57Z","timestamp":1441110237000},"page":"1585-1599","source":"Crossref","is-referenced-by-count":1,"title":["Recognizing Coverage Functions"],"prefix":"10.1137","volume":"29","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhiyi","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,9,1]]},"reference":[{"key":"atypb1","unstructured":"A. Badanidiyuru,\n                      private communication\n                      , 2013."},{"key":"atypb2","first-page":"1025","author":"Badanidiyuru A.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb3","first-page":"793","author":"Balcan M.","year":"2011","journal-title":"New York"},{"key":"atypb4","unstructured":"D. Bertsimas and J. Tsitsiklis,\n                      Introduction to Linear Optimization\n                      , Athena Scientific, Belmont, MA, 1997."},{"key":"atypb5","first-page":"267","author":"Blumrosen L.","year":"2007","journal-title":"Cambridge"},{"key":"atypb6","first-page":"170","author":"Chakrabarty D.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"S. Dughmi and J. Vondra\u0301k,\n                      Limitations of randomized mechanisms for combinatorial auctions\n                      , in Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2011, pp. 502-511.","DOI":"10.1109\/FOCS.2011.64"},{"key":"atypb9","first-page":"149","author":"Dughmi S.","year":"2011","journal-title":"New York"},{"key":"atypb10","first-page":"263","author":"Dughmi S.","year":"2011","journal-title":"New York"},{"key":"atypb11","unstructured":"V. Feldman and P. Kothari,\n                      Learning Coverage Functions and Private Release of Marginals\n                      , Conference on Learning Theory (COLT), 2014, pp. 679-702."},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"V. Feldman and J. Vondra\u0301k,\n                      Optimal bounds on approximation of submodular and xos functions by juntas\n                      , in Proceedings, FOCS, 2013.","DOI":"10.1109\/FOCS.2013.32"},{"key":"atypb13","first-page":"141","author":"Goldreich O.","year":"2009","journal-title":"New York"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/043\/04"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"atypb16","first-page":"2761","volume":"9","author":"Krause A.","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"atypb18","unstructured":"K. Mahler,\n                      Introduction to $p$-Adic numbers and their Functions\n                      , Cambridge University Press, Cambridge, 1973."},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"A. Robert,\n                      A Course in $p$-Adic Analysis\n                      , Grad. Texts Math. 198, Springer Verlag, New York, 2000.","DOI":"10.1007\/978-1-4757-3254-2"},{"key":"atypb20","unstructured":"C. Seshadhri,\n                      Open Problems2:Open Problems in Data Streams, Property Testing, and Related Topics\n                      , http:\/\/www.cs.umass.edu\/$\\sim$mcgregor\/papers\/11-openproblems.pdf (2011)."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9719-2"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140964072","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:18:08Z","timestamp":1787318288000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140964072"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140964072"],"URL":"https:\/\/doi.org\/10.1137\/140964072","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}