The list-decoding size of Fourier-sparse Boolean functions

DOI10.4230/LIPICS.CCC.2015.58MaRDI QIDQ4601822zbMATH OpenFDO

Authors Ishay Haviv, Oded Regev

Publication date 24 January 2018

Full work available at URL https://arxiv.org/abs/1504.01649

zbMATH Keywords

Fourier-sparse functionslearning theorylist-decodingproperty testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Randomized algorithms (68W20) Decoding (94B35)

Recommendations

• The list-decoding size of Fourier-sparse Boolean functions
• Testing Fourier dimensionality and sparsity
• Testing Fourier Dimensionality and Sparsity
• Near-optimal upper bound on Fourier dimension of Boolean functions in terms of Fourier sparsity
• Fourier sparsity and dimension

Cited in

(8)

• Quantum learning of concentrated Boolean functions
• Near-optimal upper bound on Fourier dimension of Boolean functions in terms of Fourier sparsity
• The list-decoding size of Fourier-sparse Boolean functions
• Fourier sparsity and dimension
• Testing Booleanity and the uncertainty principle
• Testing Fourier dimensionality and sparsity
• Testing Fourier Dimensionality and Sparsity
• A generalization of a theorem of Rothschild and van Lint

This page was built for publication: The list-decoding size of Fourier-sparse Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601822)