Learning functions of \(k\) relevant variables

DOI10.1016/j.jcss.2004.04.002zbMath1084.68057OpenAlexW2063003848MaRDI QIDQ1886314

Ryan O'Donnell, Rocco A. Servedio, Elchanan Mossel

Publication date: 18 November 2004

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.2004.04.002

zbMATH Keywords

computational learning theoryBoolean functionsPAC learning

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)

Related Items (22)

Improved time complexities for learning Boolean networks ⋮ Algorithmic Signaling of Features in Auction Design ⋮ Learning juntas in the presence of noise ⋮ A exact quantum learning algorithm for the 2-junta problem in constant time ⋮ Sample complexity of hidden subgroup problem ⋮ On the minimal Fourier degree of symmetric Boolean functions ⋮ Boolean-arithmetic equations: acquisition and uses ⋮ Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time ⋮ Quantum algorithms for learning and testing juntas ⋮ Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles ⋮ An exact quantum algorithm for the 2-junta problem ⋮ Almost Optimal Testers for Concise Representations. ⋮ Testing Juntas: A Brief Survey ⋮ Algorithms for Inference, Analysis and Control of Boolean Networks ⋮ Unnamed Item ⋮ On the degree of univariate polynomials over the integers ⋮ On derandomized composition of Boolean functions ⋮ Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem ⋮ Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions ⋮ DNF are teachable in the average case ⋮ Almost optimal distribution-free junta testing ⋮ An exact quantum polynomial-time algorithm for solving \(k\)-junta problem with one uncomplemented product

Cites Work

• Unnamed Item
• Unnamed Item
• Testing juntas
• Matrix multiplication via arithmetic progressions
• Occam's razor
• Selection of relevant features and examples in machine learning
• Polynomials with two values
• On learning monotone DNF formulae under uniform distributions
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• More efficient PAC-learning of DNF with membership queries under the uniform distribution
• An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Constant depth circuits, Fourier transform, and learnability
• Efficient noise-tolerant learning from statistical queries
• A theory of the learnable
• Learning Integer Lattices
• 10.1162/153244302760200669

This page was built for publication: Learning functions of \(k\) relevant variables