In the context of this cooperation group two conferences will take place at the ZiF.
The date of the first conference is October 25 – 29 2010.
The second conference takes place in autumn 2013.
For the first conference the following survey talks are planned:
| Ingo Althöfer: | Search in Game Trees and Game Graphs |
| Charles Colbourn: | Combinatorial t-Restrictions and Combinatorial Search |
| Lov Grover: | Quantum Searching - Old & New |
| Evangelos Kranakis: | Rendezvous Search and Exploration with Mobile Agents |
| Olgica Milenkovic: | Sublinear Compressive Sensing via Dense Belief Propagation |
In 1979 one of the first books on search (and surely the first in
Germany) was written, translated into Russian 1982, and finally into
English in 1987.
We
Perhaps the most natural example of a search problem is the task to find an unknown element in a finite set by asking questions concerning containment in a subset. In the three decades which passed since then there has been an explosion of developments in search for instance in Computer Science, Image Reconstruction, Machine Learning, Information Theory (classical and quantum theoretical), and Operation Research. Time seems to be mature for more theoretical understanding with the goal of a general Theory of Search, since there are already parallels in methods in different disciplines like data transmission over noisy channels with feedback corresponds to search with random answers and foraging of animals corresponds to search for information in the internet.
A search structure is defined by a space of objects searched for and a space of tests (questions).
In specifying a search problem performance criteria have to be chosen.
Furthermore we distinguish combinatorial and probabilistic models.
Especially important is the study of adaptive and non-adaptive
strategies as well as the analysis of their intermediate forms.
There is reason for optimism. Three decades ago it was often asked whether search is a scientific subject!
In the article “Breaking Network Logjams” in Scientific American, pages 78-85, June 2007 one finds
“On the Internet and other shared networks, information currently
gets relayed by routers—switches that operate at nodes where signaling
pathways, or links, intersect. The routers shunt incoming messages to
links heading toward the messages' final destinations. But if one wants
efficiency, are routers the best devices for these intersections? Is
switching even the right operation to perform?
Until seven years ago, few thought to ask such questions. But then
Rudolf Ahlswede of Bielefeld University in Germany, along with Ning
Cai, Shuo-Yen Robert Li and Raymond W. Yeung, all then at the
University of Hong Kong, published groundbreaking work that introduced
a new approach to distributing information across shared networks. In
this approach, called network coding, routers are replaced by coders,
which transmit evidence about messages instead of sending the messages
themselves. When receivers collect the evidence, they deduce the
original information from the assembled clues.
Although this method may sound counterintuitive, network coding,
which is still under study, has the potential to dramatically speed up
and improve the reliability of all manners of communications systems
and may well spark the next revolution in the field. Investigators are,
of course, also exploring additional avenues for improving efficiency;
as far as we know, though, those other approaches generally extend
existing methods.”
By now network coding has started a revolution in communication networks! Information flows in search are more like flows of bits in transmission than flows of water or electricity (obeying Kirchhoff's law). This is especially transparent in the first example above.
Good Luck!