Boosting and hard-core set construction
From MaRDI portal
Publication:1394786
DOI10.1023/A:1022949332276zbMath1026.68066MaRDI QIDQ1394786
Rocco A. Servedio, Adam R. Klivans
Publication date: 25 June 2003
Published in: Machine Learning (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?, 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, Query complexity in errorless hardness amplification, 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