On Worst‐Case to Average‐Case Reductions for NP Problems

DOI10.1137/S0097539705446974zbMath1118.68072OpenAlexW2048284438MaRDI QIDQ5757460

Andrej Bogdanov, Luca Trevisan

Publication date: 7 September 2007

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539705446974

zbMATH Keywords

one-way functionaverage-case complexityworst-case to average-case reduction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (31)

On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) ⋮ Guarantees for the success frequency of an algorithm for finding Dodgson-election winners ⋮ On basing search SIVP on \(\mathbf{NP}\)-hardness ⋮ Towards Non-Black-Box Separations of Public Key Encryption and One Way Function ⋮ Generic complexity of Presburger arithmetic ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Unprovable security of perfect NIZK and non-interactive non-malleable commitments ⋮ Improved hardness amplification in NP ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ On the complexity of collision resistant hash functions: new and old black-box separations ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ Hardness amplification within NP against deterministic algorithms ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Unnamed Item ⋮ Computational indistinguishability between quantum states and its cryptographic application ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ Structure Versus Hardness Through the Obfuscation Lens ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Unnamed Item ⋮ On Basing Private Information Retrieval on NP-Hardness ⋮ The Complexity of Zero Knowledge ⋮ Algebraic cryptography: new constructions and their security against provable break ⋮ 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 ⋮ Fine-Grained Cryptography

This page was built for publication: On Worst‐Case to Average‐Case Reductions for NP Problems