https://www.dagstuhl.de/09281

July 5 – 10 , 2009, Dagstuhl Seminar 09281

Search Methodologies

Organizers

Rudolf Ahlswede (Universität Bielefeld, DE)
Ferdinando Cicalese (University of Salerno, IT)
Ugo Vaccaro (University of Salerno, IT)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Seminar Proceedings DROPS
List of Participants

Summary

The main purpose of this seminar was to provide a common forum for researchers interested in the mathematical, algorithmic, and practical aspects of the problem of efficient searching, as seen in its polymorphic incarnation in the areas of computer science, communication, bioinformatics, information theory, and related fields of the applied sciences. We believe that only the on site collaboration of a variety of established and young researchers engaged in different aspects of search theory might provide the necessary humus for the identification of the basic search problems at the conceptual underpinnings of the new scientific issues in the above mentioned areas. We aim at uncovering common themes and structures among these problems, by analyzing them through interdisciplinary lens, and tools from a variety of areas, ranging from Algorithmics to Computational Complexity, from Information Theory to Combinatorics. The more recent challenges provided by the areas of Communications and Molecular Biology call for more attention at the application side of the problems. Therefore, together with the conceptual understanding and the efficient algorithmic solutions, we shall focus also on the studies of new heuristics and experimental methods as well as the theoretical understanding of the well established ones.

We carefully chose a group of outstanding researchers, of different expertise but nonetheless fluent in diverse languages of sciences. They brought their different views of the themes of the original proposal of this seminar. Through the several discussions and the two open problem sessions, we aimed at laying the basis for new perspectives, and solutions to arise.

The ubiquitous nature of group testing makes it a gold mine for investigators in Search Theory. Group testing has been proved to find applications in a surprising variety of situations, including quality control in product testing searching for files in storage systems, screening for experimental variables, data compression, computation of statistics in the data stream model, and testing for concentration of chemical and pathogenic contaminants. Group testing has been recently applied to Computational Molecular Biology, where it is used for screening library of clones with hybridization probes, and sequencing by hybridization. The contributions by P. Damaschke, G.O.H. Katona, A.J. Macula, and E. Triesch reported on some recent development in this area. In the presentation by A. Zhigljavsky, the case when tests can be affected by noise is also considered. Fault-tolerant search strategies were also considered in C. Deppe's talk. He reported on the equivalence between combinatorial channels with feedback and combinatorial search with adaptive strategies, giving new constructive bounds, when the error is proportional to the blocklength/the number of tests.

Classification

  • Data Structures / Algorithms / Complexity

Keywords

  • Search algorithms
  • Group testing
  • Fault-tolerance
  • Identification
  • Decision tree
  • Multi-access communication

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.