Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
From MaRDI portal
Publication:657913
DOI10.1016/j.jcss.2010.08.011zbMath1234.68148OpenAlexW1984649098MaRDI QIDQ657913
Jeong Han Kim, Kyomin Jung, Sung-Soon Choi
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
randomized algorithmFourier coefficientspseudo-Boolean functionWalsh analysis\(k\)-bounded functiongraph findinglearning polynomialslinkage discovery
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (2)
Satisfying more than half of a system of linear equations over GF(2): a multivariate approach ⋮ Computing the moments \(k\)-bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal query complexity bounds for finding graphs
- Some simplified NP-complete graph problems
- On the degree of Boolean functions as real polynomials
- 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
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Learning Decision Trees Using the Fourier Spectrum
- On the Fourier spectrum of monotone functions
- Learning a Hidden Matching
- Learning Theory
- Learning a Hidden Subgraph
- Automata, Languages and Programming
- Learning Theory
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Graph-Theoretic Concepts in Computer Science
- Optimal reconstruction of graphs under the additive model
This page was built for publication: Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
