### Abstract

A function defined on the Boolean hypercube is k-Fourier-sparse if it has at most knonzero Fourier coefficients. For a function f: F^{n}_{2} → ℝ 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 language | English (US) |
---|---|

Article number | 10 |

Journal | ACM Transactions on Computation Theory |

Volume | 8 |

Issue number | 3 |

DOIs | |

State | Published - May 2016 |

### Keywords

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

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computational Theory and Mathematics