文章基本信息

标题：The List-Decoding Size of Fourier-Sparse Boolean Functions
本地全文：下载
作者：Ishay Haviv ; Oded Regev
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：33
页码：58-71
DOI：10.4230/LIPIcs.CCC.2015.58
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A function defined on the Boolean hypercube is k-Fourier-sparse if it has at most k nonzero Fourier coefficients. For a function f: F_2^n -> R 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].
关键词：Fourier-sparse functions; list-decoding; learning theory; property testing