Learning Monotone Decision Trees in Polynomial Time

DOI10.1137/060669309MaRDI QIDQ3507522zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

decision treeslearningmonotone

Mathematics Subject Classification ID

Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16) Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32)

Recommendations

• On learning monotone Boolean functions under the uniform distribution
• scientific article; zbMATH DE number 1966606
• Exact learning Boolean functions via the monotone theory
• Learning Random Monotone DNF
• Learning random monotone DNF

Cited in

(41)

• Almost all monotone Boolean functions are polynomially learnable using membership queries
• Learning decision trees from random examples
• Learning functions of \(k\) relevant variables
• On the four-arm exponent for 2D percolation at criticality
• Noise sensitivity and Voronoi percolation
• Power of decision trees with monotone queries
• Learning of monotone functions with single error correction
• On the rate of convergence in quenched Voronoi percolation
• Concentration on the Boolean hypercube via pathwise stochastic analysis
• The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
• Hypercontractivity via tensor calculus
• Covert learning: how to learn with an untrusted intermediary
• Optimal bounds on approximation of submodular and XOS functions by juntas
• Optimal cryptographic hardness of learning monotone functions
• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• scientific article; zbMATH DE number 6351494 (Why is no real title available?)
• Decision Trees and Influences of Variables Over Product Probability Spaces
• Improved approximation of linear threshold functions
• scientific article; zbMATH DE number 1966606 (Why is no real title available?)
• scientific article; zbMATH DE number 1966607 (Why is no real title available?)
• scientific article; zbMATH DE number 2080450 (Why is no real title available?)
• Testing k-monotonicity
• Simple Learning Algorithms for Decision Trees and Multivariate Polynomials
• scientific article; zbMATH DE number 7626788 (Why is no real title available?)
• Beyond the low-degree algorithm: mixtures of subcubes and their applications
• An Optimal Separation of Randomized and Quantum Query Complexity
• Decision tree approximations of Boolean 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
• Testing distributional assumptions of learning algorithms
• Oded Schramm's contributions to noise sensitivity
• On the scaling limits of planar percolation
• Properly learning decision trees in almost polynomial time
• Sparse reconstruction in spin systems. I: iid spins
• On exact learning of d-monotone functions
• Geometric influences on quantum Boolean cubes
• The Pivotal Set of a Boolean Function
• Theorems of KKL, Friedgut, and Talagrand via random restrictions and log-Sobolev inequality
• Learning stochastic decision trees
• On learning monotone Boolean functions under the uniform distribution
• On learning embedded midbit functions

This page was built for publication: Learning Monotone Decision Trees in Polynomial Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3507522)