The list-decoding size of fourier-sparse Boolean functions

Ishay Haviv, Oded Regev

Research output: Contribution to journalArticle

Abstract

A function defined on the Boolean hypercube is k-Fourier-sparse if it has at most knonzero 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·klog 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].

Original languageEnglish (US)
Article number10
JournalACM Transactions on Computation Theory
Volume8
Issue number3
DOIs
StatePublished - May 2016

Keywords

  • Fourier-sparse Boolean functions
  • Learning theory
  • Property testing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The list-decoding size of fourier-sparse Boolean functions'. Together they form a unique fingerprint.

  • Cite this