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.