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

DOI10.1007/S00037-012-0056-2MaRDI QIDQ744610zbMATH OpenOpenAlexFDO

Authors 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

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
• Query complexity in errorless hardness amplification
• Query complexity in errorless hardness amplification
• Hardness Amplification Proofs Require Majority
• On the Complexity of Hardness Amplification

Cites work

• scientific article; zbMATH DE number 4191094 (Why is no real title available?)
• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• A Parallel Repetition Theorem
• Approximate list-decoding of direct product codes and uniform hardness amplification
• Boosting and hard-core set construction
• Chernoff-type direct product theorems
• Complexity of hard-core set proofs
• Hardness Amplification Proofs Require Majority
• Hardness amplification via space-efficient direct products
• Hardness amplification within NP
• Hardness amplification within NP against deterministic algorithms
• If NP languages are hard on the worst-case, then it is easy to find their hard instances
• Limitations of Hardness vs. Randomness under Uniform Reductions
• On Worst‐Case to Average‐Case Reductions for NP Problems
• On Yao's XOR-lemma
• On basing one-way functions on NP-hardness
• On the Complexity of Hardness Amplification
• On uniform amplification of hardness in NP
• One way functions and pseudorandom generators
• Pseudorandom generators without the XOR lemma
• Pseudorandomness and average-case complexity via uniform reductions
• Query complexity in errorless hardness amplification
• Random-Self-Reducibility of Complete Sets
• Randomness vs time: Derandomization under a uniform assumption
• Simple extractors for all min-entropies and a new pseudorandom generator
• Some Applications of Coding Theory in Computational Complexity
• The Complexity of Local List Decoding
• The complexity of constructing pseudorandom generators from hard functions
• Theory of Cryptography
• Uniform direct product theorems: simplified, optimized, and derandomized
• Using Nondeterminism to Amplify Hardness
• Verifying and decoding in constant depth
• Worst-Case to Average-Case Reductions Revisited
• BPP has subexponential time simulations unless EXPTIME has publishable proofs

Cited in

(10)

• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
• The power of adaptiveness and additional queries in random-self- reductions
• Erasures versus errors in local decoding and property testing
• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
• scientific article; zbMATH DE number 7758312 (Why is no real title available?)
• Query complexity in errorless hardness amplification
• Asymptotically tight worst case complexity bounds for initial-value problems with nonadaptive information
• Query complexity in errorless hardness amplification
• scientific article; zbMATH DE number 6292744 (Why is no real title available?)
• Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?

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

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