Document Open Access Logo

The List-Decoding Size of Fourier-Sparse Boolean Functions

Authors Ishay Haviv, Oded Regev

PDF
Thumbnail PDF

File

LIPIcs.CCC.2015.58.pdf
  • Filesize: 449 kB
  • 14 pages

Document Identifiers

Author Details

Ishay Haviv
Oded Regev

Cite As Get BibTex

Ishay Haviv and Oded Regev. The List-Decoding Size of Fourier-Sparse Boolean Functions. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 58-71, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CCC.2015.58

Abstract

A function defined on the Boolean hypercube is k-Fourier-sparse if it has at most k nonzero 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 [Chicago J. Theor. Comput. Sci.,2013].

Subject Classification

Keywords
  • Fourier-sparse functions
  • list-decoding
  • learning theory
  • property testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing Reed-Muller codes. IEEE Trans. on Information Theory, 51(11):4032-4039, 2005. Preliminary version in RANDOM'03. Google Scholar
  2. Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang. Learning sparse polynomial functions. In SODA, pages 500-510, 2014. Google Scholar
  3. Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff. Lower bounds for sparse recovery. In SODA, pages 1190-1197, 2010. Google Scholar
  4. Anna Bernasconi and Bruno Codenotti. Spectral analysis of Boolean functions as a graph eigenvalue problem. IEEE Trans. on Computers, 48(3):345-351, 1999. Google Scholar
  5. Arnab Bhattacharyya. Guest column: On testing affine-invariant properties over finite fields. SIGACT News, 44(4):53-72, 2013. Google Scholar
  6. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of Reed-Muller codes. In FOCS, pages 488-497, 2010. Google Scholar
  7. Avrim Blum. Learning a function of r relevant variables. In COLT, pages 731-733, 2003. Google Scholar
  8. Jean Bourgain. An improved estimate in the restricted isometry problem. In Geometric Aspects of Functional Analysis, volume 2116 of Lecture Notes in Mathematics, pages 65-70. Springer, 2014. Google Scholar
  9. Jehoshua Bruck and Roman Smolensky. Polynomial threshold functions, AC⁰ functions, and spectral norms. SIAM J. Comput., 21(1):33-42, 1992. Preliminary version in FOCS'90. Google Scholar
  10. Emmanuel J. Candès and Terence Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. on Information Theory, 52(12):5406-5425, 2006. Google Scholar
  11. Mahdi Cheraghchi, Venkatesan Guruswami, and Ameya Velingker. Restricted isometry of Fourier matrices and list decodability of random linear codes. SIAM J. Comput., 42(5):1888-1914, 2013. Preliminary version in SODA'13. Google Scholar
  12. Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In STOC, pages 25-32, 1989. Google Scholar
  13. Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer. Testing Fourier dimensionality and sparsity. SIAM J. Comput., 40(4):1075-1100, 2011. Preliminary version in ICALP'09. Google Scholar
  14. Tom Gur and Omer Tamuz. Testing Booleanity and the uncertainty principle. Chicago J. Theor. Comput. Sci., 2013, 2013. Google Scholar
  15. Ishay Haviv and Oded Regev. The restricted isometry property of subsampled Fourier matrices, 2015. Manuscript. Google Scholar
  16. Stasys Jukna. Extremal Combinatorics: With Applications in Computer Science. Texts in theoretical computer science. Springer-Verlag, second edition, 2011. Google Scholar
  17. Tali Kaufman, Shachar Lovett, and Ely Porat. Weight distribution and list-decoding size of Reed-Muller codes. IEEE Trans. on Information Theory, 58(5):2689-2696, 2012. Preliminary version in ICS'10. Google Scholar
  18. Murat Kocaoglu, Karthikeyan Shanmugam, Alexandros G. Dimakis, and Adam R. Klivans. Sparse polynomial learning and graph sketching. In NIPS, pages 3122-3130, 2014. Google Scholar
  19. Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the Fourier spectrum. SIAM J. Comput., 22(6):1331-1348, 1993. Preliminary version in STOC'91. Google Scholar
  20. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, Fourier transform, and learnability. J. ACM, 40(3):607-620, 1993. Preliminary version in FOCS'89. Google Scholar
  21. Elchanan Mossel, Ryan O'Donnell, and Rocco A. Servedio. Learning functions of k relevant variables. J. Comput. Syst. Sci., 69(3):421-434, 2004. Preliminary vesion in STOC'03. Google Scholar
  22. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  23. Mark Rudelson and Roman Vershynin. On sparse reconstruction from Fourier and Gaussian measurements. Comm. Pure Appl. Math., 61(8):1025-1045, 2008. Google Scholar
  24. Madhu Sudan. Invariance in property testing. In Property Testing - Current Research and Surveys, volume 6390, pages 211-227. Springer, 2010. Google Scholar
  25. Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and juntas. In FOCS, pages 11-20, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact