All,
Sorry for the last minute notice. Today's talk will take place at noon
over zoom
(https://gmu.zoom.us/j/93426209769?pwd=TjNmaWpvMlYxRzZGUkNzeHdPV2g3QT09).
-m
Speaker Ce Jin (MIT)
Title: Near-Optimal Quantum Algorithms for String Problems
Abstract:
We study quantum algorithms for several fundamental string problems,
including Longest Common Substring, Lexicographically Minimal String
Rotation, and Longest Square Substring. These problems have been widely
studied in the stringology literature since the 1970s, and are known to
be solvable by near-linear time classical algorithms. In this work, we
give quantum algorithms for these problems with near-optimal query
complexities and time complexities.
In this talk, I will describe our quantum algorithm for Longest Common
Substring in O~(n^{2/3}) time, improving the previous O~(n^{5/6})
algorithm by Le Gall and Seddighin (2020). Moreover, we show that the
decision version of Longest Common Substring with length threshold d (1
<= d <= n) has a quantum algorithm in n^{2/3}/d^{1/6 - o(1)} time,
interpolating between Element Distinctness and Unstructured Search. Our
algorithm uses the quantum walk framework (Ambainis 2004; Magniez,
Nayak, Roland, and Santha 2011) with a quantum version of string
synchronizing sets (Kempa and Kociumaka 2019).
|