ECCC-Report TR06-108https://eccc.weizmann.ac.il/report/2006/108Comments and Revisions published for TR06-108en-usMon, 28 Aug 2006 22:35:55 +0300
Paper TR06-108
| New connections between derandomization, worst-case complexity and average-case complexity |
Dan Gutfreund,
Amnon Ta-Shma
https://eccc.weizmann.ac.il/report/2006/108We 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
\cite{FF93,V03,BT03,AGGM06}. The bottom 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
\cite{GST05}. 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.
Mon, 28 Aug 2006 22:35:55 +0300https://eccc.weizmann.ac.il/report/2006/108