Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
DOI10.1007/S00037-012-0056-2zbMATH Open1366.68070OpenAlexW2032791464MaRDI QIDQ744610FDOQ744610
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
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- One way functions and pseudorandom generators
- Theory of Cryptography
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Randomness vs time: Derandomization under a uniform assumption
- The complexity of constructing pseudorandom generators from hard functions
- 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
- Title not available (Why is that?)
- The Complexity of Local List Decoding
- Simple extractors for all min-entropies and a new pseudorandom generator
- Worst-Case to Average-Case Reductions Revisited
- On the Complexity of Hardness Amplification
- Title not available (Why is that?)
- Hardness Amplification Proofs Require Majority
- Pseudorandom generators without the XOR lemma
- A Parallel Repetition Theorem
- On basing one-way functions on NP-hardness
- Random-Self-Reducibility of Complete Sets
- Title not available (Why is that?)
- On Worst‐Case to Average‐Case Reductions for NP Problems
- On Yao's XOR-lemma
- Hardness amplification within NP
- Boosting and hard-core set construction
- On uniform amplification of hardness in NP
- Complexity of hard-core set proofs
- Using Nondeterminism to Amplify Hardness
- Some Applications of Coding Theory in Computational Complexity
- Approximate list-decoding of direct product codes and uniform hardness amplification
- Hardness amplification within NP against deterministic algorithms
- Uniform direct product theorems: simplified, optimized, and derandomized
- Chernoff-type direct product theorems
- Hardness amplification via space-efficient direct products
- Query complexity in errorless hardness amplification
- Limitations of Hardness vs. Randomness under Uniform Reductions
- Verifying and decoding in constant depth
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
- Title not available (Why is that?)
- Query complexity in errorless hardness amplification
- Asymptotically tight worst case complexity bounds for initial-value problems with nonadaptive information
- Title not available (Why is that?)
- Query complexity in errorless hardness amplification
- 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)
