https://www.dagstuhl.de/18281

July 8 – 13 , 2018, Dagstuhl Seminar 18281

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

Organizers

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

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 8, Issue 7 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl Seminar Schedule [pdf]

Summary

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.

Goals

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.

Structure

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.

Conclusion

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
  Jrmy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti

Related Dagstuhl Seminar

Classification

  • Data Structures / Algorithms / Complexity

Keywords

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

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support