On the Complexity of Hard-Core Set Constructions

DOI10.1007/978-3-540-73420-8_18MaRDI QIDQ5428808zbMATH OpenOpenAlexFDO

Authors Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu

Publication date 28 November 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73420-8_18

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity of hard-core set proofs
• scientific article; zbMATH DE number 1306886
• Computational Randomness from Generalized Hardcore Sets
• scientific article; zbMATH DE number 1088223
• On the Complexity of Hardness Amplification

Cited in

(13)

• Boosting and hard-core set construction
• Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator
• Algorithmic construction of sets for k -restrictions
• 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
• Computational Randomness from Generalized Hardcore Sets
• Pseudoentropy: lower-bounds for chain rules and transformations
• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 1088223 (Why is no real title available?)
• scientific article; zbMATH DE number 1114037 (Why is no real title available?)
• Complexity of hard-core set proofs
• The uniform hardcore lemma via approximate Bregman projections
• Complexity bounds on general hard-core predicates.

This page was built for publication: On the Complexity of Hard-Core Set Constructions

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