Title :
Some perspectives on computational and communication complexity
Author_Institution :
Tsinghua University and The Chinese University of Hong Kong
Abstract :
Summary form only given,as follows. In past decades, the theory of computational complexity has fl ourished 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.
Conference_Titel :
Information Theory, 2006 IEEE International Symposium on
Conference_Location :
Seattle, WA
Print_ISBN :
1-4244-0505-X
DOI :
10.1109/ISIT.2006.261581