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