05. – 10. Juli 2009, Dagstuhl-Seminar 09281

Search Methodologies


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

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS


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.


  • Data Structures / Algorithms / Complexity


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


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.