Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
Speaker:Debarati Das
coming from:Charles University in Prague
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 17 July 2018
Duration:30 Minutes
Building:E1 4
The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. In this paper we study the computational problem of approximating the edit distance between a pair of strings.

The problem of computing the exact edit distance can be solved using a classical dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) show that one can compute an approximation to the edit distance within approximation factor polylog(n) in nearly linear time. Recently, Abboud and Backurs (ITCS'17) showed that under reasonable hardness assumptions the edit distance cannot be approximated within (1+o(1))-factor in truly sub-quadratic time. This raises the question whether edit distance can be approximated within constant factor in truly sub-quadratic time.

In the talk I will present our work where we affirmatively answer this question by providing an algorithm whose running time is bounded by
tilde-O(n^{2-2/7}) that approximates the edit distance up-to constant factor. Our approximation algorithm is based on a new yet simple paradigm.

Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Karl Bringmann, 07/03/2018 12:44 AM
Last modified:
Uwe Brahm/MPII/DE, 07/17/2018 07:01 AM
  • Karl Bringmann, 07/03/2018 12:44 AM -- Created document.