Communication Complexity and Applications, III (22w5124)

The Banff International Research Station will host the "Communication Complexity and Applications, III" workshop in Banff from July 24 - 29, 2022.

Communication complexity is the study of communication-efficient solutions for computational problems whose input is split amongst two or more players. Over the last four decades, it has proved itself to be among the most useful of abstractions in computer science. Communication is inherent to any computational task and quantifying this communication bounds the computational complexity of the task, e.g., the size of a data-structure that supports fast updates; the number of wires in a circuit that computes a given function; the sample complexity of a learning task; or the memory required by a streaming algorithm.

A wide range of powerful combinatorial, linear algebraic, optimization, and information-theoretic techniques have been developed for proving communication lower bounds. Over the last half decade, the development of “lifting” techniques that seek to obtain powerful communication bounds from weaker decision-tree bounds have led to some breakthroughs in central theoretical questions. At the same time, increasing sophistication in information-theoretic methods for communication complexity have led to significant advances in our understanding of data structures, algorithms on massive data and graphs, and quantum computation. The workshop brings together world experts in communication complexity and the relevant algorithmic topics with the goal of advancing both core theory and applications.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).