Campus Event Calendar
Event Entry
What and Who
Almost Optimal Edit Distance Oracles
Panagiotis Charalampopoulos
Birkbeck, University of London
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 5 October 2023
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
In this talk, we will consider the problem of preprocessing two strings S and T of total length n into a data structure that can quickly report the edit distance between any substring of S and any substring of T. I will describe a data structure with polylogarithmic query time, and almost quadratic construction time and space usage. This is conditionally optimal up to subpolynomial factors; note that just computing the edit distance between S and T cannot be done in strongly subquadratic time unless the Strong Exponential Time Hypothesis fails.
Most of the underlying techniques were originally developed for planar distance oracles and then specialised for edit distance oracles. The structure of the edit distance graph allows for a simpler exposition of the involved ideas and is further exploited to obtain a faster construction time.
The talk will be based on joint work with Paweł Gawrychowski, Shay Mozes, and Oren Weimann.
Contact
Roohani Sharma
+49 681 9325 1116
--email hidden
Virtual Meeting Details
Zoom
527 278 8807
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.
Roohani Sharma, 09/14/2023 16:54 -- Created document.