On the Fourier spectrum of symmetric Boolean functions

DOI10.1007/s00493-009-2310-zzbMath1212.42017OpenAlexW2013408443MaRDI QIDQ987559

Mihail N. Kolountzakis, Richard J. Lipton, Aranyak Mehta, Evangelos Markakis, Nisheeth K. Vishnoi

Publication date: 13 August 2010

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-009-2310-z

zbMATH Keywords

computational complexityspectrumboolean functionjunta

Mathematics Subject Classification ID

Computational learning theory (68Q32) Fourier series and coefficients in several variables (42B05)

Related Items (7)

Hamming weights of symmetric Boolean functions ⋮ On the minimal Fourier degree of symmetric Boolean functions ⋮ A divisibility approach to the open boundary cases of Cusick-Li-Stǎnicǎ's conjecture ⋮ Hadamard matrices and the spectrum of quadratic symmetric polynomials over finite fields ⋮ Recursions associated to trapezoid, symmetric and rotation symmetric functions over Galois fields ⋮ On the degree of univariate polynomials over the integers ⋮ Симметрические булевы функции и их метрические свойства

Cites Work

• Selection of relevant features and examples in machine learning
• Harmonic analysis and Boolean function complexity
• Polynomials with two values
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• More efficient PAC-learning of DNF with membership queries under the uniform distribution
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• Constant depth circuits, Fourier transform, and learnability
• Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
• Learning juntas
• A theory of the learnable
• Learning Integer Lattices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Fourier spectrum of symmetric Boolean functions