An Improved Sketching Algorithm for Edit Distance

Ce Jin, Jelani Nelson, Kewen Wu

We provide improved upper bounds for the simultaneous sketching complexity of edit distance. Consider two parties, Alice with input $x\in {\Sigma }^n$ and Bob with input $y\in {\Sigma }^n$, that sha…