TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 09281

Search Methodologies

( Jul 05 – Jul 10, 2009 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/09281

Organizers

Contact


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.


Participants
  • Rudolf Ahlswede (Universität Bielefeld, DE)
  • Ingo Althöfer (Universität Jena, DE)
  • Harout Aydinian (Universität Bielefeld, DE)
  • Ferdinando Cicalese (University of Salerno, IT)
  • Charles Colbourn (Arizona State University - Tempe, US) [dblp]
  • Peter Damaschke (Chalmers UT - Göteborg, SE) [dblp]
  • Gianluca De Marco (University of Salerno, IT)
  • Christian Deppe (Universität Bielefeld, DE)
  • Travis Gagie (University of Toronto, CA) [dblp]
  • Mordecai Golin (HKUST - Kowloon, HK) [dblp]
  • Gyula O.H. Katona (Alfréd Rényi Institute of Mathematics - Budapest, HU)
  • Kingo Kobayashi (NICT - Tokyo, JP)
  • Evangelos Kranakis (Carleton University - Ottawa, CA)
  • Anthony J. Macula (SUNY - Geneseo, US)
  • Martin Milanic (University of Primorska, SI) [dblp]
  • Olgica Milenkovic (University of Illinois - Urbana Champaign, US) [dblp]
  • Ely Porat (Bar-Ilan University - Ramat Gan, IL) [dblp]
  • Soren Riis (Queen Mary University of London, GB)
  • Eberhard Triesch (RWTH Aachen, DE)
  • Ugo Vaccaro (University of Salerno, IT)
  • Sören Werth (BSI - Bonn, DE)
  • Gabor Wiener (Budapest University of Technology & Economics, HU)
  • Anatoly Zhigljavsky (Cardiff University, GB) [dblp]

Classification
  • data structures / algorithms / complexity

Keywords
  • Search algorithms
  • group testing
  • fault-tolerance
  • identification
  • decision tree
  • multi-access communication