Organizer(s):

Mark Braverman, Princeton University

Gillat Kol, Princeton University

Description

COVID-19 Notice: This workshop has been cancelled.

Classical information theory was developed by Shannon and others to answer questions about the amount of communication needed for various data transmission tasks. It was successful in giving very precise answers in a wide variety of tasks, giving rise to the modern information theory. Within complexity theory, information-theoretic techniques turned out to be extremely versatile, leading to tight lower bounds in many different settings. Broadly speaking, information-theoretic techniques are at the core of most unconditional lower bounds for restricted models of computation. One area of impact has been communication complexity, as well as models of computation for which lower bounds can be proved using reductions to communication complexity, such as streaming algorithms and data structures. There are also examples, such as distributed inference (motivated by understanding the limits of processing statistical and machine learning tasks on a massively distributed input), where strong lower bounds are achievable through a combination of information-theoretic techniques that go beyond the classical communication complexity reductions. There still remain significant gaps in our understanding of how information-theoretic techniques apply to distributed computing models, especially when there are possible overlaps between inputs. There will be several main topics covered in this workshop:

• Advances in information-theoretic techniques for data-structure lower bounds;
• Information-theoretic tools for attaining optimal lower bounds for in distributed settings;
• Information-theoretic and communication-complexity approaches to privacy and to the constructions of cryptographic primitives;
• Interactive information theory and the problems of interactive compression and interactive coding;
• Advances in network information theory and their possible impact on theoretical computer science.

One of the goals of this workshop is building better interdisciplinary connections and encouraging collaboration between different communities, in the hope of proving stronger results and building a more unified, concurrent view of information theory.

Call For Participation

Presentation at the workshop will be mainly by invitation. Attendance at the workshop is open to all interested participants (subject to space limitations). Please register if you would like to attend this workshop.

Princeton University map (PDF).

Presented in association with the Special Focus on Lower Bounds in Computational Complexity.

Registration for this event is closed.