• Calendar

February 8, Tuesday
12:00 – 13:30

There are numerous real-world problems that translate to searching for short distances. These distances can either be explicit (think of road navigation in Google maps) or implicit (think of the distance between humans and mice as the number of changes in their genomes). In my talk, I will describe some techniques that are useful for solving various shortest paths problems efficiently. I will begin with the problem of finding a shortest path in a "grid-like" graph. This problem arrises when computing the distance (minimum number of changes) between two sequences (say two genomes), and has many applications in computational biology, speech recognition, and information retrieval. A slightly more complicated grid-like graph arises when computing the distance (minimum number of changes) between two trees (say two XML files). This has applications in computer vision, compiler optimization, and natural language processing. I will then move to layered graphs (where shortest paths can be used to decode Hidden Markov Models) and then to planar graphs (where shortest paths can be used for VLSI design and geographical routing problems). Finally, I will discuss shortest paths in general graphs, and describe how to maintain shortest paths in a (more realistic) network whose edges occasionally fail. The problem has applications in game (auction) theory and is in tight connection with classical problems such as all-pairs shortest paths. My goal is to illustrate some general techniques that are useful for many of these problems. These techniques include the efficient computation of distance products, the reduced lengths method, and the use of compression as a tool for acceleration.