| IEEE HOME
| SEARCH IEEE
| SHOP IEEE
| WEB ACCOUNT
| CONTACT IEEE
IEEE logo
IEEE Information Theory Society
Media Services
Yao Plenary Lecture, ISIT 2006

Some Perspectives on Computational and Communication Complexity

speaker photo

Andrew C. Yao
Tsinghua University
The Chinese University of Hong Kong

Videos


dialup broadband - low broadband - medium broadband - high
mov wmv mov wmv mov wmv mov wmv

Abstract

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)

Biography

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.