On the minimal Fourier degree of symmetric Boolean functions
DOI10.1007/S00493-014-2875-ZzbMATH Open1340.68042OpenAlexW2018223420MaRDI QIDQ397079FDOQ397079
Authors: Amir Shpilka, Avishay Tal 
Publication date: 14 August 2014
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-014-2875-z
Recommendations
- On the Fourier spectrum of symmetric Boolean functions
- On the Probabilistic Degrees of Symmetric Boolean Functions
- On the probabilistic degrees of symmetric Boolean functions
- On the symmetric negabent Boolean functions
- scientific article; zbMATH DE number 1076147
- On the distribution of the Fourier spectrum of Boolean functions
- Lower bounds to the complexity of symmetric Boolean functions
- scientific article; zbMATH DE number 3332496
- scientific article; zbMATH DE number 4179291
- On a conjecture for balanced symmetric Boolean functions
uniform distributionFourier coefficientsbalanced Boolean functionconsecutive prime numbersFourier spectrumnonlinear symmetric Boolean functionsymmetric juntas
Computational learning theory (68Q32) Boolean functions (06E30) Numerical methods for discrete and fast Fourier transforms (65T50)
Cites Work
- Selection of relevant features and examples in machine learning
- Title not available (Why is that?)
- The difference between consecutive primes. II
- Simple Constructions of Almost k-wise Independent Random Variables
- Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
- A spectral characterization of correlation-immune combining functions
- Learning functions of \(k\) relevant variables
- On the degree of Boolean functions as real polynomials
- Polynomials with two values
- On the Fourier spectrum of symmetric Boolean functions
- On the degree of univariate polynomials over the integers
Cited In (12)
- Pseudorandom generators for low sensitivity functions
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- 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
- Bounds on the Fourier coefficients of the weighted sum function
- On the degree of univariate polynomials over the integers
- Hamming weights of symmetric Boolean functions
- On minimal π-circuits of closing contacts for symmetric functions with threshold 2
- On the Fourier spectrum of symmetric Boolean functions
- A divisibility approach to the open boundary cases of Cusick-Li-Stǎnicǎ's conjecture
- The Degree of Balanced Elementary Symmetric Boolean Functions of <formula formulatype="inline"> <tex Notation="TeX">${{\bf 4k}+{\bf 3}}$</tex> </formula> Variables
This page was built for publication: On the minimal Fourier degree of symmetric Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q397079)
