Some Perspectives on Computational and Communication Complexity
Andrew C. Yao
The Chinese University of Hong Kong
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 talk we discuss several persistent and interwoven themes underlying many of these accomplishments. In particular we shall focus on the interplay between communication and computation which has a key role in these developments. We also speculate on promising future directions in the study of computational and communication complexity.
(Monday, July 10)
Andrew C. Yao (S'74-M'75) was born in Shanghai, China, on December 24, 1946. He received the B.S. degree in physics from National Taiwan University in 1967, the Ph.D. degree in physics from Harvard University in 1972, and the Ph.D. degree in computer science from the University of Illinois, Urbana, in 1975.
He has taught at the Massachusetts Institute of Technology and the University of California at Berkeley, and he is now a Professor of Computer Science at Stanford University. His research interests are the analysis of algorithms and computational complexity.