Complexity of hard-core set proofs

DOI10.1007/s00037-011-0003-7zbMath1255.68067OpenAlexW2084411549MaRDI QIDQ451110

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

Publication date: 21 September 2012

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-011-0003-7

zbMATH Keywords

hardness amplificationblack-box proofshard-core set

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Advice Lower Bounds for the Dense Model Theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Majority gates vs. general weighted threshold gates
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Boosting and hard-core set construction
• Boosting a weak learning algorithm by majority
• Threshold circuits of bounded depth
• On uniform amplification of hardness in NP
• Key agreement from weak bit agreement
• On the Complexity of Hardness Amplification
• On the Complexity of Hard-Core Set Constructions
• Using Nondeterminism to Amplify Hardness
• Hardness amplification within NP
• Pseudorandom generators without the XOR lemma

This page was built for publication: Complexity of hard-core set proofs