- Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281). Jérémy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti. In Dagstuhl Reports, Volume 8, Issue 7, pp. 44-61, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
This Dagstuhl Seminar will bring together researchers from the area of adaptive analysis of algorithms; the study of parameterized complexity of NP-hard problems; the area focused on compressed data structures; and the area concerned with the study of compressed indexes. While all of these subareas of algorithms and data structures, respectively, focus on ``going beyond the worst-case'' for classes of structurally restricted inputs, there has been a limited amount of interactions between them, with some results being "discovered" twice.
The goal of the seminar is to foster this interaction both during the seminar and in the future by:
- teaching one another the key techniques of one’s areas, through tutorials and short talks (with volunteers among the guests or organizers giving short tutorials on the very first day);
- discussing open problems at the intersection of the areas in varying small groups (guests will be invited to submit and present a list of results from their areas which they think could be applied to other areas); and
- compiling those techniques and open problems in a collective document realized in collaboration between volunteers among the participants (as proceedings of the seminar).
Examples of synergies include:
- techniques developed for sorting multisets and used to design compressed data structures supporting operators on permutations and functions (e.g. sorting algorithms and compression schemes taking advantage of existing subsequences of consecutive positions already sorted, or taking advantage of the potential imbalance between the frequencies of various elements of the input);
- techniques developed to study the parameterized complexity of graph algorithms which can be used to design compressed data structures for such graphs (e.g. max clique, max clique edit, etc.);
- the use of difficulty measures such as entropy for both running times and space usage (e.g. do instance optimal results on the running time yield any compression result?);
- studying which measures of compressibility of the data can also be applied to the analysis of the size of an index required in order to support additional operators on this data;
- techniques taking advantage at once of the input order, the input structure, the query order and the query structure; and others to be discovered during the seminar.
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):
- the area of adaptive analysis of algorithms;
- the study of parameterized complexity of NP-hard problems;
- the area focused on compressed data structures; and
- 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
- a first session of personal introductions, each participant presenting his expertise and themes of interests in two slides;
- a small series of technical talks, some organized a long time in advance, and some improvised "on demand"; and
- 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.
- Jérémy Barbay (University of Chile - Santiago de Chile, CL) [dblp]
- Philip Bille (Technical University of Denmark - Lyngby, DK) [dblp]
- Stefan Böttcher (Universität Paderborn, DE) [dblp]
- Luca Castelli Aleardi (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Stephane Durocher (University of Manitoba - Winnipeg, CA) [dblp]
- Johannes Fischer (TU Dortmund, DE) [dblp]
- Till Fluschnik (TU Berlin, DE) [dblp]
- Allyx Fontaine (University of Guyane - Cayenne, FR) [dblp]
- Travis Gagie (Universidad Diego Portales, CL) [dblp]
- Simon Gog (eBay Inc - San Jose, US) [dblp]
- Meng He (Dalhousie University - Halifax, CA) [dblp]
- Falko Hegerfeld (HU Berlin, DE) [dblp]
- Shunsuke Inenaga (Kyushu University - Fukuoka, JP) [dblp]
- Bart Jansen (TU Eindhoven, NL) [dblp]
- Artur Jez (University of Wroclaw, PL) [dblp]
- Seungbum Jo (Universität Siegen, DE) [dblp]
- Ahmet Kara (University of Oxford, GB) [dblp]
- David G. Kirkpatrick (University of British Columbia - Vancouver, CA) [dblp]
- Christian Knauer (Universität Bayreuth, DE) [dblp]
- Dominik Köppl (TU Dortmund, DE) [dblp]
- Stefan Kratsch (HU Berlin, DE) [dblp]
- Florian Kurpicz (TU Dortmund, DE) [dblp]
- Zsuzsanna Liptak (University of Verona, IT) [dblp]
- Sebastian Maneth (Universität Bremen, DE) [dblp]
- Ian Munro (University of Waterloo, CA) [dblp]
- Yakov Nekrich (University of Waterloo, CA) [dblp]
- Patrick K. Nicholson (Nokia Bell Labs - Dublin, IE) [dblp]
- Yoshio Okamoto (The University of Electro-Communications - Tokyo, JP) [dblp]
- Ramamohan Paturi (University of California - San Diego, US) [dblp]
- Nicola Prezza (University of Pisa, IT) [dblp]
- Rajeev Raman (University of Leicester, GB) [dblp]
- Venkatesh Raman (Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Mireille Regnier (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Giovanna Rosone (University of Pisa, IT) [dblp]
- Srinivasa Rao Satti (Seoul National University, KR) [dblp]
- Raimund Seidel (Universität des Saarlandes, DE) [dblp]
- Jouni Sirén (University of California - Santa Cruz, US) [dblp]
- Tatiana Starikovskaya (ENS - Paris, FR) [dblp]
- Rossano Venturini (University of Pisa, IT) [dblp]
- Sandra Zilles (University of Regina, CA) [dblp]
- Dagstuhl Seminar 09171: Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009-04-19 - 2009-04-24) (Details)
- data structures / algorithms / complexity
- Adaptive (analysis of) algorithms
- compressed data structures
- compressed indices
- parameterized complexity.