Computational sample complexity and attribute-efficient learning
From MaRDI portal
Publication:5918064
DOI10.1006/jcss.1999.1666zbMath0956.68132OpenAlexW1980379651MaRDI QIDQ5918064
Publication date: 27 July 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1999.1666
Related Items (6)
High-dimensional change-point estimation: combining filtering with convex optimization ⋮ On parallel attribute-efficient learning. ⋮ Computational and statistical tradeoffs via convex relaxation ⋮ Optimal testing for planted satisfiability problems ⋮ A global homogeneity test for high-dimensional linear regression ⋮ Order-Revealing Encryption and the Hardness of Private Learning
Cites Work
- Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
- Occam's razor
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Attribute-efficient learning in query and mistake-bound models
- Modern cryptography, probabilistic proofs and pseudo-randomness
- A Winnow-based approach to context-sensitive spelling correction
- Efficient distribution-free learning of probabilistic concepts
- A general lower bound on the number of examples needed for learning
- Learning in the presence of finitely or infinitely many irrelevant attributes
- Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution
- Expander codes
- Linear-time encodable and decodable error-correcting codes
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- A theory of the learnable
- Cryptographic limitations on learning Boolean formulae and finite automata
This page was built for publication: Computational sample complexity and attribute-efficient learning
