On the Fourier spectrum of symmetric Boolean functions
From MaRDI portal
Publication:987559
DOI10.1007/S00493-009-2310-ZzbMATH Open1212.42017OpenAlexW2013408443MaRDI QIDQ987559FDOQ987559
Authors: Mihail N. Kolountzakis, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, 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
Recommendations
- On the minimal Fourier degree of symmetric Boolean functions
- Towards a proof of the Fourier-entropy conjecture?
- Learning juntas
- Learning functions of \(k\) relevant variables
- Parameterized learnability of juntas
- Parameterized Learnability of k-Juntas and Related Problems
- scientific article; zbMATH DE number 1263197
- New upper bounds on the Boolean circuit complexity of symmetric functions
- scientific article; zbMATH DE number 4035741
Cites Work
- Selection of relevant features and examples in machine learning
- Learning juntas
- Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
- Title not available (Why is that?)
- Constant depth circuits, Fourier transform, and learnability
- A theory of the learnable
- Title not available (Why is that?)
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- Polynomials with two values
- An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
- Harmonic analysis and Boolean function complexity
- An invitation to additive prime number theory
- More efficient PAC-learning of DNF with membership queries under the uniform distribution
- Title not available (Why is that?)
- Learning Integer Lattices
Cited In (16)
- On Boolean functions with several flat spectra
- Hadamard matrices and the spectrum of quadratic symmetric polynomials over finite fields
- Recursions associated to trapezoid, symmetric and rotation symmetric functions over Galois fields
- Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
- Структура спектров булевых функций
- Title not available (Why is that?)
- On the degree of univariate polynomials over the integers
- Symmetric Boolean functions and their metric properties matrices of transitions of differences when using some modular groups
- Hamming weights of symmetric Boolean functions
- On the minimal Fourier degree of symmetric Boolean functions
- Bent and bent\(_4\) spectra of Boolean functions over finite fields
- Title not available (Why is that?)
- On the Fourier spectrum of functions on Boolean cubes
- A divisibility approach to the open boundary cases of Cusick-Li-Stǎnicǎ's conjecture
- Learning juntas
- Boolean functions whose Fourier transform is concentrated on the first two levels.
This page was built for publication: On the Fourier spectrum of symmetric Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987559)
