Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification

DOI10.1007/978-3-642-22935-0_32zbMath1343.68088OpenAlexW2401286301MaRDI QIDQ3088109

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_32

Mathematics Subject Classification ID

Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).

Related Items (3)

Query complexity in errorless hardness amplification ⋮ Query Complexity in Errorless Hardness Amplification ⋮ Advice Lower Bounds for the Dense Model Theorem

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
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
Hardness Amplification Proofs Require Majority
On the Complexity of Hard-Core Set Constructions
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