Visit ShanghaiTech University | 中文
HOME > News and Events > Seminars
Communication Complexity and Information Complexity
Date: 2017/3/10             Browse: 149
Seminar Topic: Communication Complexity and Information Complexity

Speaker: Tamm, Ulrich 
Time: Mar. 13, 13:30 p.m. - 14:30 p.m.
Venue:  Room 1A-200, SIST Building


Communication complexity was introduced by A. Yao (1979) in the study of parallel computation. It found, since, surprising applications in many areas of computer science as area—time tradeo in VLSI layout, separation of complexity classes, circuit complexity, and auction theory. 

A recent hot topic much related to our early work on communication complexity is information complexity. The setting can be described as follows.

Is it significantly easier to compute several instances of a problem simultaneously than sequentially? An affirmative answer to this question for communication complexity (the so-called direct-sum conjecture due to Wigderson) would have deep impact in circuit complexity. Recently, for probabilistic protocols the amortized (= simultaneous) communication complexity could be characterized as an information expression. For deterministic protocols we shall demonstrate via Kraft's inequality from data compression for some functions related to set intersection that an improvement is possible - but that this improvement is not significant.


1981 to 1991: Mathematics and Economy at the  University of Bielefeld, Germany. Diploma in Mathematics received on November 11, 1987. PhD in Mathematics received on January 11, 1991, under supervision of Prof. Rudolf Ahlswede (Shannon Lecturer 2006 of IEEE Information Theory Society). Habilitation in Mathematics on January 31, 2002 (Arbiters: Rudolf Ahlswede, Vera Pless, Alon Orlitsky, Martin Aigner)

Seminar 17002