[Colloquium] Fortnow Theory Seminars at Computer Science Tues 1 Nov

[soare]

Note,

This is exactly the one afternoon when we have the 3way logic seminars  
with
Notre Dame and Wisconsin twice per quarter.

See Antonio  Montalban web page for the schedule:

http://www.math.uchicago.edu/~antonio/Jointseminar.html

The topics are very close to the CS seminar including complexity.
This has been scheduled for several months.


Bob


==========================


On Oct 26, 2011, at 6:45 AM, Donna Brooms wrote:

> 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
>
>
> _______________________________________________
> faculty mailing list  -  faculty at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/mailman/listinfo/faculty

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20111026/16c2d329/attachment.htm