Query complexity in errorless hardness amplification

DOI10.1007/978-3-642-22935-0_58MaRDI QIDQ3088136zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

query complexityhardness amplification

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• Average Case Complete Problems
• Boosting and hard-core set construction
• Hardness Amplification Proofs Require Majority
• Hardness amplification within NP
• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
• On Yao's XOR-lemma
• One way functions and pseudorandom generators
• Using Nondeterminism to Amplify Hardness

Cited in

(10)

• Lossy functions do not amplify well
• Advice lower bounds for the dense model theorem
• Query complexity in errorless hardness amplification
• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
• Computing and Combinatorics
• On uniform amplification of hardness in NP
• scientific article; zbMATH DE number 7029312 (Why is no real title available?)
• The Zero-Error Randomized Query Complexity of the Pointer Function
• Adaptivity vs. postselection, and hardness amplification for polynomial approximation
• Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification

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)