### DIMACS - Graduate Student Combinatorics Seminar

Title: An Efficient Algorithm for Computing Ulam Distance

Speaker: **Tim Naumovitz**, Rutgers University

Date: Wednesday, September 16, 2015 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

The question of computing ulam distance arises out of a hope of
attacking the difficult related problem of computing (or approximating)
edit distance. In this talk, I'll introduce the notion of ulam distance
and show how the task of computing ulam distance can be reduced to a
discrete nearest neighbor problem. Subsequently, I'll show how one can
use techniques motivated by binary search to solve this problem. If
there's time, I might lift up the proverbial rug at the end of the talk
and look at the things I swept under it.