Bounds on the Fourier coefficients of the weighted sum function

DOI10.1016/J.IPL.2007.02.011MaRDI QIDQ2379949zbMATH OpenOpenAlexFDO

Authors Igor E. Shparlinski

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2006/617/

zbMATH Keywords

computational complexityFourier coefficientsBoolean functionweighted sums

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
• On the Fourier spectrum of functions on Boolean cubes
• On the distribution of the Fourier spectrum of Boolean functions
• On the minimal Fourier degree of symmetric Boolean functions
• Lower bounds to the complexity of symmetric Boolean functions

Cites work

• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1962823 (Why is no real title available?)
• scientific article; zbMATH DE number 1528193 (Why is no real title available?)
• scientific article; zbMATH DE number 773997 (Why is no real title available?)
• scientific article; zbMATH DE number 773999 (Why is no real title available?)
• scientific article; zbMATH DE number 774007 (Why is no real title available?)
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• Circuit and decision tree complexity of some number theoretic problems
• Constant depth circuits, Fourier transform, and learnability
• Fourier analysis for probabilistic communication complexity
• Harmonic Analysis of Polynomial Threshold Functions
• Highly nonlinear mappings
• On the Degree, Nonlinearity, Algebraic Thickness, and Nonnormality of Boolean Functions, With Developments on Symmetric Functions
• On the complexity of balanced Boolean functions
• On the degree of Boolean functions as real polynomials
• Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
• Quantum lower bounds by polynomials
• The average sensitivity of bounded-depth circuits
• The difference between consecutive primes. II

Cited in

(6)

• The simplified weighted sum function and its average sensitivity
• Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
• scientific article; zbMATH DE number 5521820 (Why is no real title available?)
• Laced Boolean functions and subset sum problems in finite fields
• Boolean nested canalizing functions: a comprehensive analysis
• On the average sensitivity of the weighted sum function

This page was built for publication: Bounds on the Fourier coefficients of the weighted sum function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2379949)