[Colloquium] THEORY SEMINAR: Mark Braverman on May 24, 2011

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, May 24, 2011
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------

Speaker:		Mark Braverman

From:		University of Toronto

Web page:	http://www.cs.toronto.edu/~mbraverm/

Title: 		Information and interactive communication

Abstract:  	Notions of entropy and information, pioneered by Shannon, have been
very powerful tools in coding theory. Coding theory aims to solve the
problem of one-way communication: sending a message from Alice to Bob
using as little communication as possible, sometimes over a noisy
channel.

We will discuss several extensions of information-theoretic notions to
the two-way communication setting. We use them to prove a direct sum
theorem for randomized communication complexity, showing that
implementing k copies of a functionality requires substantially more
communication than just one copy.

More generally, we will show that information cost I(f) can be defined
as a natural fundamental property of a functionality f. We will
describe several new tight connections between I(f), direct sum
theorems, interactive compression schemes, and amortized communication
complexity.

Host: 		Alexander Razborov

Refreshments will be served prior to the talk at 2:30 in Ryerson 255.