Christian Deppe: Combinatorial Two-Sided Search

 In this talk I give an overview of adaptive and non-adaptive strategies for two-sided search. Koopman introduced two-sided search models. In his search model, the searched object is active and can move one step after each test at most. In this talk I present a models combinatorial two-sided search.

I give search strategies and show that these strategies are optimal. I consider adaptive and non-adaptive strategies and show the surprising result that with the two-sided search  on a path graph the optimal non-adaptive search needs the same number of questions like the corresponding adaptive search strategy does.

The main results in this talk are from the papers:
A. Lebedev, C. Deppe, Non-Adaptive and Adaptive Two-Sided Search with Fast Objects, arXiv:2102.01188, 2021.
and
H. Aydinian, F.Cicalese, C. Deppe, V. Lebedev,  A Combinatorial Model ofTwo-Sided Search, International Journal of Foundations ofComputer Science 29(04), 481-504, 2018.