Seminar: January 9, 2009, 2:30pm

Scott Aaronson, MIT

The Limits of Advice

Note non-standard day and time!

Since the work of Karp and Lipton in the 1980s, complexity theorists have grown to love the /poly operator, which adds a polynomial-size "advice string" to any complexity class. But it's interesting to consider much more general kinds of "advice objects" than just strings. In this talk, I'll present a new framework for understanding the limitations of advice objects. Results include the following:

Joint work with my student Andy Drucker.