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)

Full work available at URL https://doi.org/10.1023/A:1022949332276

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

(21)

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

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)