@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 = "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",
}