BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quantum divide and conquer - Andrew Childs (University of Maryland
 )
DTSTART:20230328T140000Z
DTEND:20230328T151500Z
UID:TALK199078@talks.cam.ac.uk
CONTACT:Sergii Strelchuk
DESCRIPTION:The divide-and-conquer framework\, used extensively in classic
 al algorithm design\, recursively breaks a problem into smaller subproblem
 s\, along with some auxiliary work\, to give a recurrence relation for the
  classical complexity. We describe a quantum divide-and-conquer framework 
 that\, in certain cases\, yields quantum speedup through an analogous recu
 rrence relation for the quantum query complexity. We apply this framework 
 to obtain near-optimal quantum query complexities for various string probl
 ems\, such as (i) recognizing regular languages\; (ii) decision versions o
 f String Rotation and String Suffix\; and natural parameterized versions o
 f (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence
 . Based on joint work with Robin Kothari\, Matt Kovacs-Deak\, Aarthi Sunda
 ram\, and Daochen Wang (arXiv:2210.06419).\n\nZoom link: https://us02web.z
 oom.us/j/85407695986?pwd=TFNOcFk5RzNneUQwbGxCaU9pVEF5dz09
LOCATION:Zoom
END:VEVENT
END:VCALENDAR