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

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.