Christian Deppe: Combinatorial Two-Sided Search

Description of video

Date: 3/29/21
Speaker :Deppe Christian


     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.
    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.