Date and Time

Wednesday, October 3, 2001 - 3:30pm to 5:00pm

Location

Computer Science Small Auditorium (Room 105)

Type

Colloquium

Speaker

Andy Yao, from Princeton University

Host

David Dobkin

In past decades, the theory of computational complexity has flourished in terms of both the revelation of its internal structures and the unfolding of its numerous applications. In this paper we discuss several persistent and interwoven themes underlying many of these accomplishments. Chief amoung them are the interplay between communication and computation, the power of problem reduction, and the increasingly prominent role played by classical mathematics. We will also speculate on a few promising directions for future development of computational complexity.