Query complexity in errorless hardness amplification
DOI10.1007/978-3-642-22935-0_58zbMATH Open1343.68124OpenAlexW2270257564MaRDI QIDQ3088136FDOQ3088136
Authors:
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
Recommendations
- 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
- 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
- Hardness Amplification Proofs Require Majority
- Title not available (Why is that?)
- On Yao's XOR-lemma
- Average Case Complete Problems
- Hardness amplification within NP
- Boosting and hard-core set construction
- Using Nondeterminism to Amplify Hardness
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
Cited In (10)
- Computing and Combinatorics
- On uniform amplification of hardness in NP
- 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
- Query complexity in errorless hardness amplification
- Adaptivity vs. postselection, and hardness amplification for polynomial approximation
- The Zero-Error Randomized Query Complexity of the Pointer Function
- Lossy functions do not amplify well
- Title not available (Why is that?)
This page was built for publication: Query complexity in errorless hardness amplification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088136)
