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

Alexandr Andoni, T. S. Jayram, Mihai Patrascu

Browse the full SODA paper archive.