This workshop belongs to a series of workshops with the goal to develop a general theory of search. The first was organized by Rudolf Ahlswede, Ferdinando Cicalese, and Ugo Vaccaro in the Leibniz Institute of Dagstuhl for the period 5.-10. July 2009. Its main purpose was to provide a common forum for researchers interested in the mathematical, algorithmic, and practical aspects of efficient searching, as seen in its polymorphic incarnation in the areas of computer science, communication, information theory, operational research, bioinformatics, and related fields.
The structure of a search problem is found ubiquitously in most fields: from medicine (diagnosis), molecular biology (group testing or pooling) to generative linguistics (finding grammars generating languages), from mathematics (optimization) to computer science (indexing, sorting), from networking (routing) to transmission (identifying the message sent over a channel). However, it is much more difficult and rare that analogies (or equivalences) are found among the solutions to different search problems arising in different fields. Whether this is possible is a far-reaching question, but whenever such a correspondence is found, the bridge we build becomes a source of invaluable wealth in the different worlds of science, which find themselves suddenly connected (for a recent example see the relationships between PCP (probabilistically checkable proofs) and error-correcting codes). We are interested in deepening our understanding of these problems and we envision that some unifying principles might be disclosed. At least we want to analyze methods and techniques of searching, simplify, compare and/or merge them. One day was devoted to these activities.
The opening lecture by Rudolf Ahlswede explained that time seems to be mature for a more systematic understanding with the goal to build general theories of search. Haratyun Aydinian and Vladimir Lebedev helped as fellows in this endeavor. The following survey talks were delivered:
The first and the last survey also addressed two sided search, whereas the following contributions considered models with one-sided search, that is, the targets are passive.Contributions
Ingo Althöfer (Jena), Haratyun Aydinian (Bielefeld), Vladimir Blinovsky (Moskau), Minglai Cai (Bielefeld), Huilan Chang (Hsinchu), Hong-Bin Chen (Hsinchu), Charles Colbourn (Tempe, AZ)), Eva Czabarka (Columbia, SC), Peter Damaschke (Göteborg), Annalisa De Bonis (Fisciano), Gianluca De Marco (Fisciano), Christian Deppe (Bielefeld), Arkadii D’yachkov (Moskau), Dániel Gerbner (Budapest), Lov Kumar Grover (Murray Hill, NJ), Tobias Jacobs (Tokio), Sampath Kannan (Philadelphia, PA), Gyula O.H. Katona (Budapest), Balázs Keszegh (Budapest), Kingo Kobayashi (Tokio), Elena Konstantinova (Novosibirsk), Evangelos Kranakis (Ottawa), Vladimir Lebedev (Moskau), Ulf Lorenz (Darmstadt), Anthony J. Macula (Geneseo, NY), Martin Milanic (Koper), Ely Porat (Ramat Gan), K. Rüdiger Reischuk (Lübeck), Soren Riis (London), Yvacheslav V. Rykov (Omaha, NE), Christian Sohler (Dortmund), László Székely (Columbia, SC), Olivier Teytaud (Orsay), Eberhard Triesch (Aachen), Ugo Vaccaro (Salerno), Anna Nikitichna Voronina (Moskau)