Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NON-BLACK-BOX REDUCTION:
Reports tagged with non-black-box reduction:
TR18-138 | 10th August 2018
Shuichi Hirahara

Non-black-box Worst-case to Average-case Reductions within NP

Revisions: 1

There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of NP: Several results suggest that black-box worst-case to average-case reductions are not likely to be used for reducing any worst-case problem outside coNP to a distributional NP problem.

This paper overcomes the barrier. We ... more >>>




ISSN 1433-8092 | Imprint