Robust Simulations and Significant Separations

Lance Fortnow, Rahul Santhanam

We define and study a new notion of "robust simulations" between complexity classes which is intermediate between the traditional notions of infinitely-often and almost-everywhere,…