The List-Decoding Size of Fourier-Sparse Boolean Functions

DOI10.1145/2898439zbMath1427.68362OpenAlexW1836151211MaRDI QIDQ4973855

Ishay Haviv, Oded Regev

Publication date: 6 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5060/

zbMATH Keywords

learning theoryproperty testingFourier-sparse Boolean functions

Mathematics Subject Classification ID

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

Related Items (2)

Sample complexity of hidden subgroup problem ⋮ Unnamed Item

This page was built for publication: The List-Decoding Size of Fourier-Sparse Boolean Functions