Bounds on the Fourier coefficients of the weighted sum function

DOI10.1016/J.IPL.2007.02.011zbMATH Open1184.68270OpenAlexW2122674593MaRDI QIDQ2379949FDOQ2379949

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/

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

zbMATH Keywords

computational complexityFourier coefficientsBoolean functionweighted sums

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
• Title not available (Why is that?)
• 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
• The simplified weighted sum function and its average sensitivity

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)