Learning functions of \(k\) relevant variables
From MaRDI portal
Publication:1886314
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
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
