Boosting and hard-core set construction

DOI10.1023/A:1022949332276MaRDI QIDQ1394786zbMATH OpenFDO

Authors Adam R. Klivans, Rocco A. Servedio

Publication date 25 June 2003

Published in Machine Learning (Search for Journal in Brave)

zbMATH Keywords

boostingcomputational complexityhard core set construction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The uniform hardcore lemma via approximate Bregman projections
• On the Complexity of Hard-Core Set Constructions
• Boosting in the presence of noise
• scientific article; zbMATH DE number 1804120
• Boosting a weak learning algorithm by majority

Cited in

(14)

• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
• Nonuniform indistinguishability and unpredictability hardcore lemmas: new proofs and applications to pseudoentropy
• Computational Randomness from Generalized Hardcore Sets
• scientific article; zbMATH DE number 7754310 (Why is no real title available?)
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• A complete characterization of statistical query learning with applications to evolvability
• Complexity of hard-core set proofs
• Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
• scientific article; zbMATH DE number 7758312 (Why is no real title available?)
• Query complexity in errorless hardness amplification
• Query complexity in errorless hardness amplification
• Advice lower bounds for the dense model theorem
• Amplifying the security of functional encryption, unconditionally
• Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?

This page was built for publication: Boosting and hard-core set construction

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