New connections between derandomization, worst-case complexity and average-case complexity
Dan Gutfreund, Amnon Ta‐Shma · 2006
We show that a mild derandomization assumption together with the worst-case hardness of NP implies the average-case hardness of a language in non-deterministic quasi-polynomial time. Previously such connections were only known for high classes such as EXP and PSPACE. There has been a long line of research trying to explain our failure in proving worst-case to average-case reductions within NP [FF93, Vio03, BT03, AGGM06]. The bot-tom line of this research is essentially that (under plausible assumptions) black-box techniques cannot prove such results. Indeed, our proof is not black-box, as it uses a non-black-box reduction of Gutfreund, Shaltiel and Ta-Shma [GSTS05]. Furthermore, we prove using the same arguments as the above mentioned negative results, that this reduction cannot be done in a black-box way (again, under a plausible assumption). Thus our techniques show a way to bypass black-box impossibility arguments regarding worst-case to average-case reductions.