Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-154 | 11th December 2005 00:00

Non-Uniform Hardness for NP via Black-Box Adversaries


Authors: Albert Atserias
Publication: 13th December 2005 08:00
Downloads: 1851


We 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..

ISSN 1433-8092 | Imprint