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