Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification

DOI10.1007/s00037-012-0056-2zbMath1366.68070OpenAlexW2032791464MaRDI QIDQ744610

Sergei Artemenko, Ronen Shaltiel

Publication date: 25 September 2014

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.221.32

zbMATH Keywords

hardness amplificationblack-box reductions

Mathematics Subject Classification ID

Related Items (4)

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Erasures versus errors in local decoding and property testing ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of hard-core set proofs
• Hardness amplification within NP against deterministic algorithms
• Chernoff-type direct product theorems
• One way functions and pseudorandom generators
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Boosting and hard-core set construction
• Randomness vs time: Derandomization under a uniform assumption
• The complexity of constructing pseudorandom generators from hard functions
• Hardness amplification via space-efficient direct products
• Pseudorandomness and average-case complexity via uniform reductions
• If NP languages are hard on the worst-case, then it is easy to find their hard instances
• On basing one-way functions on NP-hardness
• Query Complexity in Errorless Hardness Amplification
• On Yao’s XOR-Lemma
• Random-Self-Reducibility of Complete Sets
• The Complexity of Local List Decoding
• Limitations of Hardness vs. Randomness under Uniform Reductions
• Simple extractors for all min-entropies and a new pseudorandom generator
• Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification
• On uniform amplification of hardness in NP
• Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
• Worst-Case to Average-Case Reductions Revisited
• On the Complexity of Hardness Amplification
• A Parallel Repetition Theorem
• Hardness Amplification Proofs Require Majority
• Some Applications of Coding Theory in Computational Complexity
• Using Nondeterminism to Amplify Hardness
• On Worst‐Case to Average‐Case Reductions for NP Problems
• Theory of Cryptography
• Hardness amplification within NP
• Pseudorandom generators without the XOR lemma

This page was built for publication: Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification