Learning Monotone Decision Trees in Polynomial Time
From MaRDI portal
Publication:3507522
DOI10.1137/060669309zbMath1147.68028OpenAlexW2029370139MaRDI QIDQ3507522
Ryan O'Donnell, Rocco A. Servedio
Publication date: 19 June 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/060669309
Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16)
Related Items (18)
An Optimal Separation of Randomized and Quantum Query Complexity ⋮ Improved approximation of linear threshold functions ⋮ Upper bounds on the one-arm exponent for dependent percolation models ⋮ Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions ⋮ Hypercontractivity via tensor calculus ⋮ Covert learning: how to learn with an untrusted intermediary ⋮ Oded Schramm's contributions to noise sensitivity ⋮ On the scaling limits of planar percolation ⋮ The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture ⋮ Decision Trees and Influences of Variables Over Product Probability Spaces ⋮ On the four-arm exponent for 2D percolation at criticality ⋮ Unnamed Item ⋮ Noise sensitivity and Voronoi percolation ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas ⋮ Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity ⋮ On the rate of convergence in quenched Voronoi percolation ⋮ Concentration on the Boolean hypercube via pathwise stochastic analysis ⋮ Unnamed Item
This page was built for publication: Learning Monotone Decision Trees in Polynomial Time
