[Colloquium] THEORY SEMINAR TODAY IN RYERSON 255

[Meridel Trimble]

THEORY SEMINAR

Speaker: Rahul Santhanam

Title: Hierarchy Theorems for Probabilistic Polynomial Time

Time: Thursday, October 7th, 12:15pm
Place: Ryerson 255 (1100 E. 58th St.)
 
Speaker's Homepage: http://people.cs.uchicago.edu/~rahul/
  
Abstract: We show a hierarchy theorem for probabilistic polynomial time with one
bit of advice. Specifically, we show that for any real numbers 1 <= r < s, there
is a language in BPTIME(n^s)/1 but not in BPTIME(n^r)/1. Our result builds upon
and improves an earlier result of Barak using log(log(n)) bits of advice.

We also show that for any r >= 1, there is a language decidable on average in
BPP but not decidable on average in BPTIME(n^r).

This is joint work with Lance Fortnow.
  
If you have questions, please contact Meridel at 4-9873 or 
mtrimble at tti-c.org