Recent results on worst-case to average-case reductions for NP
Speaker: Dan Gutfreund , Hebrew University
Date: December 6 2005
Time: 4:15PM to 5:30PM
Location: 32-G449 Patil/Kiva, Stata Ctr
Host: Ronitt Rubinfeld, TOC, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: Abstract:
We prove that if some NP-complete language is worst-case hard, then for every
efficient algorithm trying to decide the language, there exists some
polynomially samplable distribution that is hard for it. That is, the algorithm
often errs on inputs from this distribution. This is the first worst-case to
average-case reduction for NP of any kind.
We stress however, that this does not mean that there exists one fixed
samplable distribution that is hard for every efficient algorithm, which is a
pre-requisite assumption needed for OWF and cryptography (even if not a
sufficient one). Nevertheless, we do show that if NP is worst-case hard then:
1. There exists a fixed distribution, samplable in quasi-polynomial-time that
is hard for every efficient algorithm. And,
2. Under a mild derandomization assumption, there exists a language in
nondeterministic quasi-polynomial-time for which the uniform distribution over
its instances is hard for every efficient algorithm.
Our reductions make non-black-box use of the adversary, and by Bogdanov and
Trevisan (FOCS 2003) this seems to be inevitable. Our key lemma, which may be
of independent ineterst, is the following: given a description of an efficient
algorithm that fails to solve SAT in the worst-case, we can efficiently
generate at most three formulas (of increasing lengths) such that the algorithm
errs on at least one of them.
Based on joint works with Ronen Shaltiel and Amnon Ta-Shma.
See other events that are part of Theory Colloquium Fall 2005
See other events happening in December 2005
