Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities

Alexandr Andoni, T. S. Jayram, Mihai Patrascu

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]. Prom 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 ℓd∞(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.
BibTeX
@inproceedings{andoni2010lower,
  author = {Alexandr Andoni and T. S. Jayram and Mihai Patrascu},
  title = {{Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities}},
  booktitle = {SODA},
  year = {2010},
  doi = {10.1137/1.9781611973075.17},
}

Loading related content...

Figure