A new view on worst-case to average-case reductions for NP problems

DOI10.1007/978-3-319-08783-2_18zbMATH Open1425.68132arXiv1312.2490OpenAlexW2963655442MaRDI QIDQ2920459FDOQ2920459

Authors: Thomas Holenstein, Robin Künzler

Publication date: 26 September 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We study the result by Bogdanov and Trevisan (FOCS, 2003), who show that under reasonable assumptions, there is no non-adaptive worst-case to average-case reduction that bases the average-case hardness of an NP-problem on the worst-case complexity of an NP-complete problem. We replace the hiding and the heavy samples protocol in [BT03] by employing the histogram verification protocol of Haitner, Mahmoody and Xiao (CCC, 2010), which proves to be very useful in this context. Once the histogram is verified, our hiding protocol is directly public-coin, whereas the intuition behind the original protocol inherently relies on private coins.

Full work available at URL: https://arxiv.org/abs/1312.2490

Recommendations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (2)

This page was built for publication: A new view on worst-case to average-case reductions for NP problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2920459)