期刊
ACM TRANSACTIONS ON COMPUTATION THEORY
卷 8, 期 3, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2898439
关键词
Fourier-sparse Boolean functions; learning theory; property testing
资金
- Simons Collaboration on Algorithms and Geometry
- National Science Foundation (NSF) [CCF-1320188]
A function defined on the Boolean hypercube is k-Fourier-sparse if it has atmost knonzero 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 [2013].
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据