|COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR II|
|Topic:||Relativized Separations of Worst-Case and Average-Case Complexities for NP|
|Affiliation:||University of California, San Diego; Member, School of Mathematics|
|Date:||Tuesday, March 8|
|Time/Room:||10:30am - 12:30pm/S-101|
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.