CS Forum: "Strong inapproximability of the shortest reset word"
Speaker: Paweł Gawrychowski from Institute of Informatics, University of Warsaw, Poland
20.08.2015 / 15:00 - 16:15
Place: T2, CS Building
Abstract:
The Cerny conjecture states that every n-state synchronizing automaton has a reset word of length at most (n−1)^2. We study the hardness of finding short reset words. It is known that the exact version of the problem, i.e., finding the shortest reset word, is NP-hard and coNP-hard, and complete for the DP class, and that approximating the length of the shortest reset word within a factor of O(logn) is NP-hard [Gerbush and Heeringa, CIAA'10], even for the binary alphabet [Berlinkov, DLT'13]. We significantly improve on these results by showing that, for every ϵ>0, it is NP-hard to approximate the length of the shortest reset word within a factor of n^{1−ϵ}. This is essentially tight since a simple O(n)-approximation algorithm exists.
Speaker: Paweł Gawrychowski received his PhD from the University of Wroclaw for work on pattern matching in compressed texts. Then he was a post-doc at the Max Planck Institute for Informatics in Saarbruecken and currently is a post-doc at the University of Warsaw.
Host:
Przemysław Uznański