Communication Complexity and Applications, II (17w5147)

The Banff International Research Station will host the "Communication Complexity and Applications, II" workshop from March 19th to March 24th, 2017.

Communication complexity is the study of communication-efficient solutions for computational problems whose input is split amongst two or more players. Over the last three 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 couple of years, remarkable progress has been made towards extending and unifying these approaches. However, foundational questions such as the "direct-sum" problem and "log-rank" conjecture remain. Furthermore, new applications including analyzing massive graphs, sub-linear time algorithms, and quantum computation necessitate new communication models and techniques. The workshop will bring together world experts in communication complexity and the relevant algorithmic topics with the goal of addressing these challenges and proposing new directions of research.

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 disc
iplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineeri
ng 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).