Computing Edit Distance
Speaker
Ryan Martin
Iowa State University
https://orion.math.iastate.edu/rymartin/
Description
We will continue the edit distance problem, giving further results and more insight into the proofs. The concept of colored regularity graphs of Alon and Stav are used to compute edit distance without direct use of Szemeredi's regularity lemma. In addition, there is a weighted version of Turan's theorem which may be of independent interest.
Event Topic
Discrete Applied Math Seminar