On the minimal Fourier degree of symmetric Boolean functions

DOI10.1007/s00493-014-2875-zzbMath1340.68042OpenAlexW2018223420MaRDI QIDQ397079

Avishay Tal, Amir Shpilka

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

zbMATH Keywords

Fourier coefficientsuniform distributionFourier spectrumbalanced Boolean functionconsecutive prime numbersnonlinear symmetric Boolean functionsymmetric juntas

Mathematics Subject Classification ID

Computational learning theory (68Q32) Numerical methods for discrete and fast Fourier transforms (65T50) Boolean functions (06E30)

Related Items (7)

Hamming weights of symmetric Boolean functions ⋮ Unnamed Item ⋮ 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 ⋮ Improved bounds for quantified derandomization of constant-depth circuits and polynomials

Cites Work

• Unnamed Item
• On the Fourier spectrum of symmetric Boolean functions
• Selection of relevant features and examples in machine learning
• Polynomials with two values
• On the degree of Boolean functions as real polynomials
• Learning functions of \(k\) relevant variables
• The Difference Between Consecutive Primes, II
• Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
• A spectral characterization of correlation-immune combining functions
• Simple Constructions of Almost k-wise Independent Random Variables
• On the degree of univariate polynomials over the integers

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