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

DOI10.1016/J.JCSS.2010.08.011zbMATH Open1234.68148OpenAlexW1984649098MaRDI QIDQ657913FDOQ657913

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

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

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)

Cites Work

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

Cited In (7)

• 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
• On the Fourier tails of bounded functions over the discrete cube
• Bounds on the Fourier coefficients of the weighted sum function
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• 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
• On the Fourier tails of bounded functions over the discrete cube

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)