08. – 13. Juli 2018, Dagstuhl-Seminar 18281

Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices


Jérémy Barbay (University of Chile – Santiago de Chile, CL)
Johannes Fischer (TU Dortmund, DE)
Stefan Kratsch (HU Berlin, DE)
Srinivasa Rao Satti (Seoul National University, KR)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Report, Volume 8, Issue 7 Dagstuhl Report
Dagstuhl's Impact: Dokumente verfügbar
Programm des Dagstuhl-Seminars [pdf]


Seminar 18281, about the ``Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices'', gathered researchers from four distinct research areas (with some researchers having results in up to three such areas, but none in all four):

  1. the area of adaptive analysis of algorithms;
  2. the study of parameterized complexity of NP-hard problems;
  3. the area focused on compressed data structures; and
  4. the area concerned with the study of compressed indices.


The intuition behind gathering people from such diverse communities was that while all of these subareas of algorithms and data structures focus on "going beyond the worst-case" for classes of structurally restricted inputs, there has been a limited amount of interactions between them, and some results have been "discovered" twice. Therefore, the main goal of the seminar was to share knowledge and make joint progress through dedicated survey talks and plenty of time for discussions and work on open problems.


The seminar consisted of

  1. a first session of personal introductions, each participant presenting his expertise and themes of interests in two slides;
  2. a small series of technical talks, some organized a long time in advance, and some improvised "on demand"; and
  3. a larger series of presentation of open problems, with ample time left for the participants to gather and work on such open problems.


Most participants concurred that they learned a lot from the seminar, and acquired new contacts to foster further collaborations. In particular, interactions between the adaptive analysis of algorithms and the study of the parameterized complexity of NP-hard problems seemed relevant to the recent development of conditional lower bounds for problems classically solved in polynomial time, an approach referred to as "Fine Grained Analysis" or "FPT in P".

Generally, it appears that the seminar struck a good balance between scheduled sessions for survey talks and presentation of open problems as well as free time for discussion and interaction. During the free time, many smaller groups got together for work on open problems or for informal presentations of more specialist topics with a smaller audience. We think that this setup, along with the longer than usual round of introductions on the first day, was very successful at bringing together the different research areas.

Summary text license
  Creative Commons BY 3.0 Unported license
  Jérémy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti

Related Dagstuhl-Seminar


  • Data Structures / Algorithms / Complexity


  • Adaptive (analysis of) algorithms
  • Compressed data structures
  • Compressed indices
  • Parameterized complexity.


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.


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