Seminar of Theoretical Computer Science - Stefan Dobrev (22.3.2019)

Friday 22.3.2019 at 11:00, room M/213

19. 03. 2019 09.28 hod.
By: Rastislav Královič

Stefan Dobrev (Matematický ústav SAV):
Exploration of High-Dimensional Grids by Finite State Machines

Abstrakt:
We consider the problem of finding a treasure at an unknown point of an n-dimensional infinite grid, n ≥ 3, by initially collocated finite state agents (scouts/robots). Recently, the problem has been well characterized for 2 dimensions for deterministic as well as randomized agents, both in synchronous and semi-synchronous models. It has been conjectured that n + 1 randomized agents are necessary to solve this problem in the n-dimensional grid. We disprove the conjecture in a strong sense: we show that three randomized synchronous agents suffice to explore an n-dimensional grid for any n. Our algorithm is optimal in terms of the number of the agents.

web: https://beda.dcs.fmph.uniba.sk/seminar