Amirbehshad Shahrasbi

activity

20132022

most citedSynchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound

46 citations · 96 across the 8 of their papers we have counts for

collaborators

Showing cs.DSShow all

1 paper · 1 filter

cs.DS2018★ 20 cited

Near-Linear Time Insertion-Deletion Codes and (1+ $ε$ )-Approximating Edit Distance via Indexing

Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi

We introduce fast-decodable indexing schemes for edit distance which can be used to speed up edit distance computations to near-linear time if one of the strings is indexed by an i…

Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing

Near-Linear Time Insertion-Deletion Codes and (1+ $ε$ )-Approximating Edit Distance via Indexing