BEGIN:VCALENDAR
VERSION:2.0
X-WR-CALNAME;VALUE=TEXT:Seminar: Andrew Childs (University of Maryland): "Quantum divide and conquer"
PRODID:-//Harvard events data//EN
BEGIN:VEVENT
UID:event_1663719_0
SUMMARY:Seminar: Andrew Childs (University of Maryland): "Quantum divide and conquer"
DESCRIPTION:<p>	<strong><drupal-media data-entity-type="media" data-entity-uuid="a52119b2-5adb-4f68-af76-18e2a6adaad0" alt="Andrew Childs" data-view-mode="hwp_small"></drupal-media><br>Speaker: </strong>Andrew Childs (University of Maryland)<br><strong>Title:</strong> Quantum divide and conquer<br><strong>Abstract:</strong> The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem into smaller subproblems, 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 recurrence relation for the quantum query complexity. We apply this framework to obtain near-optimal quantum query complexities for various string problems, such as (i) recognizing regular languages; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence.</p><p>	Based on joint work with Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, and Daochen Wang (arXiv:2210.06419).</p><p>	 </p>
LOCATION:https://harvard.zoom.us/j/779283357?pwd=MitXVm1pYUlJVzZqT3lwV2pCT1ZUQT09
STATUS:CONFIRMED
DTSTART:20230228T143000Z
DTEND:20230228T143000Z
END:VEVENT
END:VCALENDAR