Projects per year
Abstract / Description of output
We define and study a new notion of “robust simulations” between complexity classes which is intermediate between the traditional notions of infinitelyoften and almosteverywhere, as well as a corresponding notion of “significant separations”. A language L has a robust simulation in a complexity class C if there is a language in C which agrees with L on arbitrarily large polynomial stretches of input lengths. There is a significant separation of L from C if there is no robust simulation of L ∈ C.
The new notion of simulation is a cleaner and more natural notion of simulation than the infinitelyoften notion. We show that various implications in complexity theory such as the collapse of PH if NP = P and the KarpLipton theorem have analogues for robust simulations. We then use these results to prove that most known separations in complexity theory, such as hierarchy theorems, fixed polynomial circuit lower bounds, timespace tradeoffs, and the recent theorem of Williams, can be strengthened to significant separations, though in each case, an almost everywhere separation is unknown.
Proving our results requires several new ideas, including a completely different proof of the hierarchy theorem for nondeterministic polynomial time than the ones previously known.
The new notion of simulation is a cleaner and more natural notion of simulation than the infinitelyoften notion. We show that various implications in complexity theory such as the collapse of PH if NP = P and the KarpLipton theorem have analogues for robust simulations. We then use these results to prove that most known separations in complexity theory, such as hierarchy theorems, fixed polynomial circuit lower bounds, timespace tradeoffs, and the recent theorem of Williams, can be strengthened to significant separations, though in each case, an almost everywhere separation is unknown.
Proving our results requires several new ideas, including a completely different proof of the hierarchy theorem for nondeterministic polynomial time than the ones previously known.
Original language  English 

Title of host publication  Automata, Languages and Programming 
Subtitle of host publication  38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 48, 2011, Proceedings, Part I 
Publisher  Springer Berlin Heidelberg 
Pages  569580 
Number of pages  12 
Volume  6755 
ISBN (Electronic)  9783642220067 
ISBN (Print)  9783642220050 
DOIs  
Publication status  Published  2011 
Fingerprint
Dive into the research topics of 'Robust Simulations and Significant Separations'. Together they form a unique fingerprint.Projects
 1 Finished

Hierarchies, Circuit Lower Bounds and Pseudorandomness
Santhanam, R.
1/10/10 → 31/12/12
Project: Research