Some Perspectives on Computational Complexity
Date and Time
Wednesday, October 3, 2001 - 3:30pm to 5:00pm
Computer Science Small Auditorium (Room 105)
Andy Yao, from Princeton University
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.