{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:39:41Z","timestamp":1787341181632,"version":"build-2736575974"},"reference-count":58,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>We investigate the approximability of several classes of real-valued functions by functions of a small number of variables (juntas). Our main results are tight bounds on the number of variables required to approximate a function $f:\\{0,1\\}^n \\rightarrow [0,1]$ within $\\ell_2$-error $\\epsilon$ over the uniform distribution: (a) If $f$ is submodular, then it is $\\epsilon$-close to a function of $O(\\frac{1}{\\epsilon^2} \\log \\frac{1}{\\epsilon})$ variables. This is an exponential improvement over previously known results [V. Feldman, P. Kothari, and J. Vondr\u00e1k, JMLR Workshop Conf. Proc., 35 (2013), pp. 711--740]. We note that $\\Omega(\\frac{1}{\\epsilon^2})$ variables are necessary even for linear functions. (b) If $f$ is fractionally subadditive (XOS) it is $\\epsilon$-close to a function of $2^{O(1\/\\epsilon^2)}$ variables. This result holds for all functions with low total $\\ell_1$-influence and is a real-valued generalization of Friedgut's theorem for Boolean functions. We show that $2^{\\Omega(1\/\\epsilon)}$ variables are necessary even for XOS functions. As applications of these results, we provide learning algorithms over the uniform distribution. For XOS functions, we give a probably approximately correct learning algorithm that runs in time $2^{1\/\\mathrm{poly}(\\epsilon)} \\mathrm{poly}(n)$. For submodular functions we give an algorithm in the more demanding probably mostly approximately correct (PMAC) learning model [M. F. Balcan and N. Harvey, preprint, arXiv:1008.2159, 2012] which requires a multiplicative $(1+\\gamma)$ factor approximation with probability at least $1-\\epsilon$ over the target distribution. Our uniform distribution algorithm runs in time $2^{1\/\\mathrm{poly}(\\gamma\\epsilon)} \\mathrm{poly}(n)$. This is the first algorithm in the PMAC model that can achieve a constant approximation factor arbitrarily close to 1 for all submodular functions (even over the uniform distribution). It relies crucially on our bounds for approximation by juntas. As follows from the lower bounds in the above paper by Feldman, Kothari, and Vondr\u00e1k both of these algorithms are close to optimal. We also give applications for proper learning, testing, and agnostic learning of these classes.<\/jats:p>","DOI":"10.1137\/140958207","type":"journal-article","created":{"date-parts":[[2016,6,29]],"date-time":"2016-06-29T17:28:58Z","timestamp":1467221338000},"page":"1129-1170","source":"Crossref","is-referenced-by-count":8,"title":["Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas"],"prefix":"10.1137","volume":"45","author":[{"given":"Vitaly","family":"Feldman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Vondr\u00e1k","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,6,29]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"atypb2","first-page":"1025","author":"Badanidiyuru A.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb3","first-page":"4","volume":"23","author":"Balcan M.F.","year":"2012","journal-title":"JMLR Workshop Conf. Proc."},{"key":"atypb4","unstructured":"M.F. Balcan and N. Harvey,\n                      Submodular Functions: Learnability, Structure, and Optimization\n                      , preprint, arXiv:1008.2159, 2012."},{"key":"atypb5","first-page":"463","volume":"3","author":"Bartlett P.","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"W. Beckner,\n                      Inequalities in Fourier analysis\n                      , Ann. of Math. (2), 102 (1975), pp. 159-182.","DOI":"10.2307\/1970980"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"M. Ben-Or and N. Linial,\n                      Collective coin flipping, robust voting schemes and minima of banzhaf values\n                      , in 26th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1985, pp. 408-416.","DOI":"10.1109\/SFCS.1985.15"},{"key":"atypb8","unstructured":"E. Blais, K. Onak, R. Servedio, and G. Yaroslavtsev,\n                      private communication\n                      , 2013."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.5802\/aif.357"},{"key":"atypb10","first-page":"208","author":"Boucheron S.","year":"2003","journal-title":"Berlin"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200005)16:3<277::AID-RSA4>3.0.CO;2-1"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02785861"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"atypb14","first-page":"1586","author":"Cheraghchi M.","year":"2012","journal-title":"Philadelphia"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0045-5"},{"key":"atypb16","unstructured":"I. Dinur and E. Friedgut,\n                      Lecture Notes for Analytical Methods in Combinatorics and Computer-Science (Lecture 5)\n                      , http:\/\/www.cs.huji.ac.il\/$\\sim$analyt\/ (2005)."},{"key":"atypb17","first-page":"437","author":"Dinur I.","year":"2006","journal-title":"New York"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"atypb19","first-page":"1064","author":"Dobzinski S.","year":"2006","journal-title":"Philadelphia"},{"key":"atypb20","first-page":"69","author":"Edmonds J.","year":"1970","journal-title":"New York"},{"key":"atypb21","first-page":"41","author":"Feige U.","year":"2006","journal-title":"New York"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"U. Feige, V. Mirrokni, and J. Vondr\u00e1k,\n                      Maximizing non-monotone submodular functions\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2007, pp. 461-471.","DOI":"10.1109\/FOCS.2007.29"},{"key":"atypb23","first-page":"679","volume":"35","author":"Feldman V.","year":"2014","journal-title":"JMLR Workshop Conf. Proc."},{"key":"atypb24","first-page":"711","volume":"35","author":"Feldman V.","year":"2013","journal-title":"JMLR Workshop Conf. Proc."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"atypb26","first-page":"65","author":"Frank A.","year":"1997","journal-title":"UK"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009809"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-8858(02)00024-6"},{"key":"atypb29","first-page":"535","author":"Goemans M.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20115"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"atypb32","first-page":"527","author":"Gopalan P.","year":"2008","journal-title":"New York"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0068-6"},{"key":"atypb34","first-page":"265","author":"Guestrin C.","year":"2005","journal-title":"New York"},{"key":"atypb35","first-page":"803","author":"Gupta A.","year":"2011","journal-title":"New York"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"atypb37","first-page":"68","author":"Kahn J.","year":"1988","journal-title":"Washington, DC"},{"key":"atypb38","first-page":"793","author":"Kakade S.","year":"2008","journal-title":"Amsterdam"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022615600103"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1109\/18.930926"},{"key":"atypb42","first-page":"2","author":"Krause A.","year":"2006","journal-title":"New York"},{"key":"atypb43","first-page":"235","volume":"9","author":"Krause A.","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"atypb44","first-page":"1010","author":"Krauthgamer R.","year":"2006","journal-title":"Philadelphia"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1137\/0222080"},{"key":"atypb46","first-page":"235","author":"Lov\u00e1sz L.","year":"1983","journal-title":"Berlin"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1043"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20145"},{"key":"atypb49","first-page":"462","volume":"4","author":"Nisan N.","year":"1992","journal-title":"Comput. Complexity"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1137\/060669309"},{"key":"atypb51","first-page":"98","author":"Queyranne M.","year":"1995","journal-title":"Philadelphia"},{"key":"atypb52","doi-asserted-by":"crossref","unstructured":"S. Raskhodnikova and G. Yaroslavtsev,\n                      Learning pseudo-boolean k-DNF and submodular functions\n                      , in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2013.","DOI":"10.1137\/1.9781611973105.98"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.04.003"},{"key":"atypb54","first-page":"195","author":"Seshadhri C.","year":"2011","journal-title":"Innovations in Computer Science"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"atypb56","unstructured":"V. Vapnik,\n                      Statistical Learning Theory\n                      , Wiley-Interscience, New York, 1998."},{"key":"atypb57","first-page":"67","author":"Vondr\u00e1k J.","year":"2008","journal-title":"New York"},{"key":"atypb58","unstructured":"J. Vondr\u00e1k,\n                      A Note on Concentration of Submodular Functions\n                      , preprint, arXiv:1005.2791v1, 2010."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140958207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:08:52Z","timestamp":1787339332000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140958207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/140958207"],"URL":"https:\/\/doi.org\/10.1137\/140958207","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}