ECCC-Report TR05-154https://eccc.weizmann.ac.il/report/2005/154Comments and Revisions published for TR05-154en-usTue, 13 Dec 2005 08:00:34 +0200
Paper TR05-154
| Non-Uniform Hardness for NP via Black-Box Adversaries |
Albert Atserias
https://eccc.weizmann.ac.il/report/2005/154We may believe SAT does not have small Boolean circuits.
But is it possible that some language with small circuits
looks indistiguishable from SAT to every polynomial-time
bounded adversary? We rule out this possibility. More
precisely, assuming SAT does not have small circuits, we
show that for every language $A$ with small circuits,
there exists a probabilistic polynomial-time algorithm
that makes black-box queries to $A$, and produces, for a
given input length, a Boolean formula on which $A$
differs from SAT. A key step for obtaining this result is
a new proof of the main result by Gutfreund, Shaltiel,
and Ta-Shma reducing average-case hardness to worst-case
hardness via uniform adversaries \emph{that know the
algorithm they fool}. The new adversary we construct has
the feature of being black-box on the algorithm it fools,
so it makes sense in the non-uniform setting as well. Our
proof makes use of a refined analysis of the learning
algorithm of Bshouty et al..
Tue, 13 Dec 2005 08:00:34 +0200https://eccc.weizmann.ac.il/report/2005/154