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.68148MaRDI 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 algorithm; Fourier coefficients; pseudo-Boolean function; Walsh analysis; \(k\)-bounded function; graph finding; learning polynomials; linkage discovery
68Q32: Computational learning theory
68Q25: Analysis of algorithms and problem complexity
68W20: Randomized algorithms
Related Items
Computing the moments \(k\)-bounded pseudo-Boolean functions over Hamming spheres of arbitrary radius in polynomial time, Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
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
