http://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

Annette Beyer for administrative matters

Michael Gerke for scientific matters

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 ones 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.

    License
      Creative Commons BY 3.0 DE
      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.

    Book exhibition

    Books from the participants of the current Seminar 

    Book exhibition in the library, ground floor, during the seminar week.

    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