You are here: MADALGO Events show

MADALGO Theory Seminar

MADALGO Seminar: Qin Zhang (Indiana University Bloomington): "Edit Distance: Sketching, Streaming and Document Exchange"

2016.09.12 | Lotte Damsgaard

Date Fri 30 Sep
Time 14:15 15:00
Location Nygaard 395



Edit Distance: Sketching, Streaming and Document Exchange


We show that in the document exchange problem, where Alice holds $x \in \{0,1\}^n$ and Bob holds $y \in \{0,1\}^n$, Alice can send Bob a message of size $O(K(\log^2 K+\log n))$ bits such that Bob can recover $x$ using the message and his input $y$ if the edit distance between $x$ and $y$ is no more than $K$, and output ``error'' otherwise. Both the encoding and decoding can be done in time $\tilde{O}(n+\poly(K))$. This result significantly improves the previous communication bounds under polynomial encoding/decoding time. We also show that in the referee model, where Alice and Bob hold $x$ and $y$ respectively, they can compute sketches of $x$ and $y$ of sizes $\poly(K \log n)$ bits (the encoding), and send to the referee, who can then compute the edit distance between $x$ and $y$ together with all the edit operations if the edit distance is no more than $K$, and output ``error'' otherwise (the decoding). To the best of our knowledge, this is the {\em first} result for sketching edit distance using $\poly(K \log n)$ bits. Moreover, the encoding phase of our sketching algorithm can be performed by scanning the input string in one pass. Thus our sketching algorithm also implies the {\em first} streaming algorithm for computing edit distance and all the edits exactly using $\poly(K \log n)$ bits of space.


Lars Arge