Errorless versus error-prone average-case complexity

Conference item

We consider the question of whether errorless and error-prone notions of average-case hardness are equivalent, and make several contributions.
First, we study this question in the context of hardness for NP, and connect it to the long-standing open question of whether there are instance checkers for NP. We show that there is an efficient non-uniform non-adaptive reduction from errorless to error-prone heuristics for NP if and only if there is an efficient non-uniform average-case non-adaptive instance-checker for NP. We also suggest an approach to proving equivalence of the two notions of average-case hardness for PH.
Second, we show unconditionally that error-prone average-case hardness is equivalent to errorless average-case hardness for P against NC¹ and for UP ∩ coUP against P.
Third, we apply our results about errorless and error-prone average-case hardness to get new equivalences between hitting set generators and pseudo-random generators.

Authors: Hirahara, S; Santhanam, R;

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Dagstuhl Publishing
• Volume: 215
• Pages: 1-23
• Article number: 84
• Series: LIPIcs - Leibniz International Proceedings in Informatics
• Series number: 13
• Publication date: 2022-01-26
• Acceptance date: 2021-10-31
• Event title: 13th Innovations in Theoretical Computer Science Conference
• Event series: Innovations in Theoretical Computer Science Conference
• Event location: Berkeley
• Event website: http://itcs-conf.org/index.html
• Event start date: 2022-01-31
• Event end date: 2022-02-03
• DOI: 10.4230/LIPIcs.ITCS.2022.84
• EISSN: 1868-8969
• Language: English
• Keywords: pseudorandomness; average-case complexity; instance checker; FFR