The edit distance between two strings (aka Levenshtein distance) is the
number of character insertions, deletions and substitutions required to
transform one string to the other. I will focus on strings which are
permutations (or rankings), i.e. comprise of distinct characters.

I will first present a low-distortion embedding of edit distance on
permutations (aka the Ulam metric) [joint work with Moses Charikar, and
a new proof joint with Parikshit Gopalan and T.S. Jayram]. I will then
discuss a data stream algorithm for estimating the "sortedness" of a
permutation, measured by its edit distance from a monotone permutation
[joint with Parikshit Gopalan, T.S. Jayram, and Ravi Kumar].