Relativized Separations of Worst-Case and Average-Case Complexities for NP

COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR II
Topic:Relativized Separations of Worst-Case and Average-Case Complexities for NP
Speaker:Russell Impagliazzo
Affiliation:University of California, San Diego; Member, School of Mathematics
Date:Tuesday, March 8
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/impagliazzo/08mar11

Non-relativization of complexity issues can be interpreted as giving evidence that these issues cannot be resolved by “black-box” techniques. We show that the assumption $DistNP \subseteq AvgP$ does not imply that $NP\subseteq BPP$ by relativizing techniques. More precisely, we give an oracle relative to which the assumption holds but the conclusion fails. Moreover, relative to our oracle, $NP \cap co-NP$ requires exponential sized circuits. We also show that average-case easiness for $NP$ does not imply average-case easiness for the polynomial hierarchy.