APL Talk: Faster Treasure Hunt and Better Strongly Universal Exploration Sequences

user warning: Got error 28 from storage engine query: SELECT DISTINCT t.* FROM drupal_term_node r INNER JOIN drupal_term_data t ON r.tid = t.tid INNER JOIN drupal_vocabulary v ON t.vid = v.vid LEFT JOIN drupal_forum_access fa ON t.tid = fa.tid LEFT JOIN drupal_acl acl_fa ON acl_fa.name = t.tid AND acl_fa.module = 'forum_access' LEFT JOIN drupal_acl_user aclu_fa ON aclu_fa.acl_id = acl_fa.acl_id AND aclu_fa.uid = 0 WHERE ((fa.grant_view >= 1 AND fa.rid IN (1)) OR fa.tid IS NULL OR aclu_fa.uid = 0) AND ( r.vid = 16066 )ORDER BY v.weight, t.weight, t.name in /var/www/dikutal.dk/modules/taxonomy/taxonomy.module on line 632.
Skrevet af Dybber, 15. februar 2012 - 16:10
Dato: 
17. Februar 2012 - 13:00 - 14:00

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

Place: Lille UP1, Universitetsparken 1, 2100 Kbh. Ø.

Abstract:

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

Bio

Prof. Dr. Qin Xin graduated with his PhD (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.