Query Complexity in Errorless Hardness Amplification

DOI10.1007/978-3-642-22935-0_58zbMath1343.68124OpenAlexW2270257564MaRDI QIDQ3088136

No author found.

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_58

zbMATH Keywords

hardness amplificationquery complexity

Mathematics Subject Classification ID

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

Related Items (4)

Query complexity in errorless hardness amplification ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ 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
• One way functions and pseudorandom generators
• Boosting and hard-core set construction
• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
• On Yao’s XOR-Lemma
• Average Case Complete Problems
• Hardness Amplification Proofs Require Majority
• Using Nondeterminism to Amplify Hardness
• Hardness amplification within NP

This page was built for publication: Query Complexity in Errorless Hardness Amplification