On the Fourier spectrum of monotone functions
From MaRDI portal
Publication:4371686
DOI10.1145/234533.234564zbMath0882.68060OpenAlexW2168115971MaRDI QIDQ4371686
Christino Tamon, Nader H. Bshouty
Publication date: 22 January 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1880/45749
Related Items (30)
On learning monotone DNF under product distributions ⋮ On PAC learning algorithms for rich Boolean function classes ⋮ On the nonlinearity of monotone Boolean functions ⋮ Learning intersections and thresholds of halfspaces ⋮ Improved approximation of linear threshold functions ⋮ On the Fourier-Walsh spectrum of the Moebius function ⋮ Proofs of Work from worst-case assumptions ⋮ Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions ⋮ Learning random monotone DNF ⋮ On derandomization and average-case complexity of monotone functions ⋮ Parameterized Learnability of k-Juntas and Related Problems ⋮ A complete characterization of statistical query learning with applications to evolvability ⋮ Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions ⋮ The difficulty of Monte Carlo approximation of multivariate monotone functions ⋮ Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles ⋮ Monotone Boolean functions capture their primes ⋮ On the complexity of compressing obfuscation ⋮ Inferring Boolean functions via higher-order correlations ⋮ Optimal query complexity bounds for finding graphs ⋮ Hardness amplification within NP ⋮ The Decomposition Tree for analyses of Boolean functions ⋮ Unconditional lower bounds for learning intersections of halfspaces ⋮ Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity ⋮ Parameterized learnability of juntas ⋮ Proper learning of \(k\)-term DNF formulas from satisfying assignments ⋮ The learnability of exclusive-or expansions based on monotone DNF formulas ⋮ Learning DNF from random walks ⋮ Unnamed Item ⋮ Agnostically Learning Boolean Functions with Finite Polynomial Representation ⋮ On learning monotone Boolean functions under the uniform distribution
This page was built for publication: On the Fourier spectrum of monotone functions
