@inproceedings{f0757d5a408c42b5b63e7606aaacd256,

title = "The list-decoding size of Fourier-sparse Boolean functions",

abstract = "A function defined on the Boolean hypercube is k-Fourier-sparse if it has at most k nonzero Fourier coefficients. For a function f: Fn2→ ℝ and parameters k and d, we prove a strong upper bound on the number of k-Fourier-sparse Boolean functions that disagree with f on at most d inputs. Our bound implies that the number of uniform and independent random samples needed for learning the class of k-Fourier-sparse Boolean functions on n variables exactly is at most O(n · k log k). As an application, we prove an upper bound on the query complexity of testing Booleanity of Fourier-sparse functions. Our bound is tight up to a logarithmic factor and quadratically improves on a result due to Gur and Tamuz (Chicago J. Theor. Comput. Sci., 2013).",

keywords = "Fourier-sparse functions, Learning theory, List-decoding, Property testing",

author = "Ishay Haviv and Oded Regev",

note = "Funding Information: We thank Adi Akavia, Shachar Lovett, and Eric Price for useful discussions and comments. Supported by the Simons Collaboration on Algorithms and Geometry and by the National Science Foundation (NSF) under Grant No. CCF-1320188. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF. Publisher Copyright: {\textcopyright} Ishay Haviv and Oded Regev; licensed under Creative Commons License CC-BY.; 30th Conference on Computational Complexity, CCC 2015 ; Conference date: 17-06-2015 Through 19-06-2015",

year = "2015",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.CCC.2015.58",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "58--71",

editor = "David Zuckerman",

booktitle = "30th Conference on Computational Complexity, CCC 2015",

}