DLS - Andy Yao

Andy Yao
Tsinghua University

Communication Complexity and Its Applications
 

photo of Andy Yao
Abstract: For any function f(x, y), its communication complexity is the minimum number of bits needed to be exchanged between two parties holding integers x and y respectively. Invented 30 years ago, communication complexity has been a central research area in theoretical computer science with rich applications to algorithmic problems in data structure, circuit complexity, and cryptography. In this talk, we give an overview of communication complexity, high-lighting notable recent results and the diverse mathematical techniques needed to obtain these results.

Biography: Professor Yao is currently a Professor of Computer Science at Tsinghua University, Beijing. Between 1975 and 2004, he held faculty positions at MIT, Stanford, UC Berkeley and Princeton University. He is recipient of the prestigious A.M. Turing Award in 2000 for his fundamental contributions to the theory of computation, including communication complexity, pseudorandom number generation, and quantum communication.

Other honours include the Polya Prize, the Knuth Prize, and several honorary degrees. He is a member of the U.S. National Academy of Sciences, the American Academy of Arts and Sciences, and the Chinese Academy of Sciences.