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:

1. 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);
2. 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
3. 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:

1. 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);
2. 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.);
3. 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?);
4. 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;
5. 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.

Creative Commons BY 3.0 DE

Jérémy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti

• 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]