Communication Complexity and Applications (14w5164)

The Banff International Research Station will host the "Communication Complexity and Applications" workshop from August 24th to August 29th, 2014.

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 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).