Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions

DOI10.1016/J.JCSS.2010.08.011MaRDI QIDQ657913zbMATHOpenAlexFDO

Authors Sung-Soon Choi, Kyomin Jung, Jeong Han Kim

Publication date 11 January 2012

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2010.08.011

zbMATH Keywords

randomized algorithmFourier coefficientspseudo-Boolean functionWalsh analysis\(k\)-bounded functiongraph findinglearning polynomialslinkage discovery

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Randomized algorithms (68W20)

Recommendations

• Bounds on the Fourier coefficients of the weighted sum function
• On the minimal Fourier degree of symmetric Boolean functions
• On the Fourier spectrum of monotone functions
• On the Fourier tails of bounded functions over the discrete cube
• On the Fourier spectrum of symmetric Boolean functions

Cites work

• scientific article; zbMATH DE number 5957397 (Why is no real title available?)
• scientific article; zbMATH DE number 5957469 (Why is no real title available?)
• scientific article; zbMATH DE number 194544 (Why is no real title available?)
• scientific article; zbMATH DE number 774007 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Automata, Languages and Programming
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Graph-Theoretic Concepts in Computer Science
• Learning Decision Trees Using the Fourier Spectrum
• Learning Theory
• Learning Theory
• Learning a Hidden Matching
• Learning a Hidden Subgraph
• Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
• More efficient PAC-learning of DNF with membership queries under the uniform distribution
• On the Fourier spectrum of monotone functions
• On the degree of Boolean functions as real polynomials
• Optimal query complexity bounds for finding graphs
• Optimal reconstruction of graphs under the additive model
• Some simplified NP-complete graph problems

Cited in

(7)

• On the Fourier tails of bounded functions over the discrete cube
• On the Fourier tails of bounded functions over the discrete cube
• An upper bound on the number of iterations for transforming a Boolean function of degree greater or equal than 4 to a function of degree 3
• Computing the moments \(k\)-bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time
• Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Bounds on the Fourier coefficients of the weighted sum function

This page was built for publication: Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions

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