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

Motivation

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.