Nexus of Information and Computation Theories
Distributed Computation and Communication Theme
February 1 – 12, 2016

Titles, Abstracts, and Video Links

Entire YouTube Playlist

Final Schedule

Overview: Distributed computation has been an active area of research since the 1970’s in both the information theory and the theory of computer science communities. Both have proposed different frameworks known as ‘‘coding for computing’’ and ‘‘computational complexity,’’ respectively, and we aim to explore their interplay.

Canonical Problems: What is the minimum amount of information that needs to flow across a network to achieve a specific goal such as computing a function or achieving consensus? In multi-party computation, what are the tradeoffs between the amount of exchanged information and the amount of computation? What are the relationships between various models of multi-party computation, such as the Number-On-Forehead and the Blackboard (multi-cast) models?

Keywords: multi-terminal coding for computing, including communication complexity, distributed source coding, gossip.

Theme Organizers