https://www.dagstuhl.de/22301

24. – 29. Juli 2022, Dagstuhl-Seminar 22301

Algorithmic Aspects of Information Theory

Organisatoren

Phokion G. Kolaitis (University of California – Santa Cruz, US & IBM Research, US)
Andrei Romashchenko (University of Montpellier – LIRMM, FR & CNRS, FR)
Milan Studený (The Czech Academy of Sciences – Prague, CZ)
Dan Suciu (University of Washington – Seattle, US)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team

Dokumente

Teilnehmerliste
Gemeinsame Dokumente
Programm des Dagstuhl-Seminars [pdf]

Motivation

Constraints on entropies constitute the “laws of information theory”. These constraints go well beyond Shannon’s basic information inequalities, as they include not only information inequalities that cannot be derived from Shannon’s basic inequalities, but also conditional inequalities and disjunctive inequalities that are valid for all entropic functions. By now, there is an extensive body of research on constraints on entropies and their applications to different areas of mathematics and computer science. So far, however, little progress has been made on the algorithmic aspects of information theory. In fact, even fundamental questions about the decidability of information inequalities and their variants remain open to date.

Recently, research in different applications has demonstrated a clear need for algorithmic solutions to questions in information theory. These applications include: finding tight upper bounds on the answer to a query on a relational database, the homomorphism domination problem and its uses in query optimization, the conditional independence implication problem, soft constraints in databases, group-theoretic inequalities, and lower bounds on the information ratio in secret sharing. Thus far, the information-theory community has had little interaction with the communities where these applications have been studied or with the computational complexity community. The main goal of this Dagstuhl Seminar is to bring together researchers from the aforementioned communities and to develop an agenda for studying algorithmic aspects of information theory, motivated from a rich set of diverse applications. By using the algorithmic lens to examine the common problems and by transferring techniques from one community to the other, we expect that bridges will be created and some tangible progress on open questions may be made.

In addition to tutorials and talks, there will be ample time for discussions, informal interactions, and open problem sessions aiming to produce a comprehensive list of problems in algorithmic aspects of information theory.

Motivation text license
  Creative Commons BY 4.0
  Phokion G. Kolaitis, Andrej E. Romashchenko, Milan Studeny, and Dan Suciu

Classification

  • Computational Complexity
  • Databases
  • Information Theory

Keywords

  • Information theory
  • Information inequalities
  • Conditional independence structures
  • Database query evaluation and containment
  • Decision problems

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.