[Colloquium] [Staff] Theory Seminars at Computer Science (CANCELLED)

[Donna Brooms]

  ~CANCELLED~

COMPUTER SCIENCE

The University of Chicago

THEORY SEMINAR

_______________________

Date:	Tuesday, November 1, 2011

Time:	3 p.m.

Place:	Ryerson 251, 1100 E. 58th Street

______________________

Speaker:	Lance Fortnow

From:		Northwestern University

Title:		Robust Simulations and Significant Separations


Abstract:	 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,
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 in C.

The new notion of simulation is a cleaner and more natural
notion of simulation than the infinitely-often notion. We show
that various implications in complexity theory such as the
collapse of PH if \NP = P and the Karp-Lipton 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, time-space 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
new  proof of the nondeterministic-time hierarchy theorem.

This is joint work with Rahul Santhanam (Edinburgh) from the recent ICALP conference.
The paper is available at http://www.cs.uchicago.edu/~fortnow/papers/robust.pdf

_____________________________________________________________________________________________

*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*

Persons who need assistance should call 773-702-6614


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20111027/8bdc4b72/attachment.htm