Name
Abstract | ||
|---|---|---|
We prove that any sketching protocol for edit distance achieving a constant approximation requires nearly logarithmic (in the strings' length) communication complexity. This is an exponential improvement over the previous, doubly-logarithmic, lower bound of [Andoni-Krauthgamer, FOCS'07]. Our lower bound also applies to the Ulam distance (edit distance over non-repetitive strings). In this special case, it is polynomially related to the recent upper bound of [Andoni-Indyk-Krauthgamer, SODA'09]. From a technical perspective, we prove a direct-sum theorem for sketching product metrics that is of independent interest. We show that, for any metric X that requires sketch size which is a sufficiently large constant, sketching the max-product metric ld∞(X) requires Ω(d) bits. The conclusion, in fact, also holds for arbitrary two-way communication. The proof uses a novel technique for information complexity based on Poincaré inequalities and suggests an intimate connection between non-embeddability, sketching and communication complexity. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.5555/1873601.1873618 | SODA |
Keywords | Field | DocType |
arbitrary two-way communication,ulam distance,type inequality,information complexity,independent interest,constant approximation,product metrics,lower bound,direct-sum theorem,communication complexity,intimate connection,metric x,exponential improvement,competitive analysis,edit distance,upper bound,computational geometry,motion planning | Edit distance,Discrete mathematics,Combinatorics,Upper and lower bounds,Computational geometry,Jaro–Winkler distance,Communication complexity,Logarithm,Product metric,Mathematics,Special case | Conference |
Volume | ISBN | Citations |
135 | 978-0-89871-698-6 | 9 |
PageRank | References | Authors |
0.53 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandr Andoni | 1 | 1684 | 81.72 |
| T. S. Jayram | 2 | 1373 | 75.87 |
| Mihai Patrascu | 3 | 1153 | 49.84 |