TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 22301

Algorithmic Aspects of Information Theory

( Jul 24 – Jul 29, 2022 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/22301

Organizers

Contact



Schedule

Summary

The goal of this seminar was to bring together researchers from several communities who share an interest in the methods and the uses of information theory. Participants included experts in information theory, databases, secret sharing, algorithms, and combinatorics. There were four tutorials, two from the information theory community and two from the database community, that helped define a common language and a common set of problems. There were several contributed talks, from experts in all these fields. The proof of one of the major open problems in information theory was announced at the workshop by not one, but, by two researchers, namely Cheuk Ting Li and Geva Yashfe, who used quite different techniques to independently solve this open problem. Overall, the workshop was a success.

Organization of the Seminar

The seminar was held between July 25-29, 2022 (Monday to Friday), and had 25 on-site participants, and 8 remote participants. Since the participants represented quite diverse communities, we started the first day with an introduction of each participant. The four tutorials were scheduled during the first two days: two tutorials on information inequalities and conditional independence were given by László Csirmaz and Milan Studený, and two tutorials on different aspects of database theory were given by Marcelo Arenas and Hung Ngo. All four tutorials were very well received, with many questions and lively discussions during and after the tutorials. There were 18 contributed talks in total, spread over all 5 days of the seminar. We scheduled two sessions to discuss open problems: one on Tuesday afternoon, and one on Thursday afternoon. The seminar concluded with an hour-long discussion assessing the seminar and contemplating future directions. Our collector, Tobias Boege, recorded all open problems, and later typed them for inclusion in this report.

Outcomes of the Seminar

There are several major outcomes:

  • Having participants with very diverse backgrounds enabled us to exchange interesting ideas and problems. Information theorists became inspired by problems that arise in database research, while database theoreticians learned tools and techniques from information theory; almost all talks raised algorithmic questions that inspired people from the algorithms community.
  • We have assembled a list of open problems, which we included here, and we also plan to publish independently. We hope that this list will help define the community interested in the algorithmic aspects of information theory, and will also inspire young researchers to contribute to this emerging area.
  • At the end of the workshop the participants expressed a lot of interest in continuing to have some organized forum for discussing problems in information theory. One of us (Andrei Romashchenko) is planning to organize regular talks, to be made publicly available online, via Zoom.
  • Everyone was happily surprised that one major problem in information theory was essentially settled during this seminar. The problem asks whether the implication problem for conditional independence statements is decidable. This problem has been studied since at least the early 80's, and has resisted any prior attempts at settling it. Cheuk Ting Li announced a proof of the undecidability of this problem, and presented the high-level structure of the proof; he had posted on arXiv a paper describing the proof just a few weeks before the seminar. Geva Yashfe had solved a different open problem: he showed that it is undecidable whether a given (2n −1)-dimensional vector is an almost entropic vector. Through discussions at the seminar, he realized that his proof can be extended to also prove that the implication problem for conditional independences is undecidable. He gave a presentation of his proof on the blackboard, during the seminar.

Acknowledgements

We are grateful to the Scientific Directorate and to the staff of the Schloss Dagstuhl – Leibniz Center for Informatics for their support of this seminar. We also wish to express our sincere thanks to Dr. Tobias Boege for collecting the abstracts of the talks and compiling the list of open problems.

Copyright Phokion G. Kolaitis, Andrei Romashchenko, Milan Studený, and Dan Suciu

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.

Copyright Phokion G. Kolaitis, Andrej E. Romashchenko, Milan Studeny, and Dan Suciu

Participants
On-site
  • Marcelo Arenas (PUC - Santiago de Chile, CL) [dblp]
  • Albert Atserias (UPC Barcelona Tech, ES) [dblp]
  • Amos Beimel (Ben Gurion University - Beer Sheva, IL)
  • Tobias Andreas Boege (MPI für Mathematik in den Naturwissenschaften, DE)
  • Janneke Bolt (TU Eindhoven, NL)
  • Laszlo Csirmaz (Alfréd Rényi Institute of Mathematics - Budapest, HU)
  • Kyle Deeds (University of Washington - Seattle, US)
  • Oriol Farras (Universitat Rovira i Virgili - Tarragona, ES)
  • Yuval Filmus (Technion - Haifa, IL) [dblp]
  • Emirhan Gürpinar (University of Montpellier & CNRS, FR)
  • Miika Hannula (University of Helsinki, FI) [dblp]
  • Peter Harremoës (Niels Brock Copenhagen Business College, DK)
  • Batya Kenig (Technion - Haifa, IL) [dblp]
  • Phokion G. Kolaitis (University of California – Santa Cruz, US & IBM Research, US) [dblp]
  • Rostislav Matveev (MPI für Mathematik in den Naturwissenschaften, DE)
  • Fabio Mogavero (University of Naples, IT) [dblp]
  • Hung Ngo (relationalAI - Berkeley, US) [dblp]
  • Carles Padró (UPC Barcelona Tech, ES)
  • Andrei Romashchenko (University of Montpellier – LIRMM, FR & CNRS, FR)
  • Sudeepa Roy (Duke University - Durham, US) [dblp]
  • Alexander Shen (University of Montpellier & CNRS, FR) [dblp]
  • Milan Studený (The Czech Academy of Sciences - Prague, CZ)
  • Dan Suciu (University of Washington - Seattle, US) [dblp]
  • John MacLaren Walsh (Drexel University - Philadelphia, US)
  • Lele Wang (University of British Columbia - Vancouver, CA)
  • Geva Yashfe (The Hebrew University of Jerusalem, IL)
Remote:
  • Mahmoud Abo Khamis (relationalAI - Berkeley, US)
  • George Konstantinidis (University of Southampton, GB)
  • Cheuk Ting Li (The Chinese University of Hong Kong, HK)
  • Frederique Oggier (Nanyang TU - Singapore, SG)
  • Soren Riis (Queen Mary University of London, GB)
  • Yufei Tao (The Chinese University of Hong Kong, HK) [dblp]
  • Nikolay K. Vereshchagin (NRU Higher School of Economics - Moscow, RU) [dblp]
  • Raymond W. Yeung (The Chinese University of Hong Kong, HK)

Classification
  • Computational Complexity
  • Databases
  • Information Theory

Keywords
  • information theory
  • information inequalities
  • conditional independence structures
  • database query evaluation and containment
  • decision problems