Faster Treasure Hunt and Better Strongly Universal Exploration Sequences

APL Group Talk by Qin Xin, Ph.D., Associate Professor, Faculty of Science and Technology, University of the Faroe Islands


In this talk, we study the explicit deterministic treasure hunt problem in an $n$-vertex network. This problem was firstly introduced by Ta-Shma, and Zwick in [1][SODA'07]. It is a variant of the well known rendezvous problem in which one of the robot (the treasure) is always stationary. We show an $O(n^{c(1+\frac{1}{\lambda})})$-time solution for this problem, which significantly improves the currently best known result of running time $O(n^{2c})$ in [1], where $c$ is a fixed constant from the construction of an universal exploration sequence in [1,2], $\lambda$ is a constant integer and $\lambda \gg 1$. The treasure hunt problem motivates the study of strongly universal exploration sequences. We give a better explicit construction of strongly universal exploration sequences than the one in [1].

[1] A. Ta-Shma, and U. Zwick. Deterministic rendezvous, treasure hunts and strongly universal exploration sequences, in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 599-608, 2007.

[2] O. Reingold. Undirected ST-connectivity in logspace. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC, pp. 376-385, 2005 (best paper in STOC 2005).


Prof. Dr. Qin Xin graduated with his Ph.D (Oct. 2002 - Nov. 2004) in the Department of Computer Science at the University of Liverpool, UK, in December 2004. Currently, he is working at the Faculty of Science and Technology at the University of Faroe Islands (UFI), Faroe Islands as an associate professor.

His main research focus is on design and analysis of sequential, parallel and distributed algorithms for various communication and optimization problems in wireless networks and information management systems. Moreover, he also investigates the combinatorial optimization problems with applications in Bioinformatics and Data Mining.