  Given its status as a classic problem and its importance to both
theoreticians and practitioners, edit distance provides an excellent lens
through which to understand how the theoretical analysis of algorithms impacts
practical implementations. From an applied perspective, the goals of
theoretical analysis are to predict the empirical performance of an algorithm
and to serve as a yardstick to design novel algorithms that perform well in
practice. In this paper, we systematically survey the types of theoretical
analysis techniques that have been applied to edit distance and evaluate the
extent to which each one has achieved these two goals. These techniques include
traditional worst-case analysis, worst-case analysis parametrized by edit
distance or entropy or compressibility, average-case analysis, semi-random
models, and advice-based models. We find that the track record is mixed. On one
hand, two algorithms widely used in practice have been born out of theoretical
analysis and their empirical performance is captured well by theoretical
predictions. On the other hand, all the algorithms developed using theoretical
analysis as a yardstick since then have not had any practical relevance. We
conclude by discussing the remaining open problems and how they can be tackled.
