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.
Date and Time
Wednesday October 3, 2001 3:30pm -
5:00pm
Location
Computer Science Small Auditorium (Room 105)
Event Type
Speaker
Andy Yao, from Princeton University
Host
David Dobkin