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.