Worst-Case to Average-Case Reductions Revisited

DOI10.1007/978-3-540-74208-1_41zbMath1171.68498OpenAlexW2140343994WikidataQ62398470 ScholiaQ62398470MaRDI QIDQ3603494

Dan Gutfreund, Amnon Ta-Shma

Publication date: 17 February 2009

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-540-74208-1_41

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Unnamed Item ⋮ The Complexity of Zero Knowledge ⋮ 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

This page was built for publication: Worst-Case to Average-Case Reductions Revisited