Computer Science Colloquium, 2008-2009

Abstract:

While some computational problems require ad hock solutions, it is often the case that efficient solutions to many different problems rely on the same speedup technique. In my talk, I will give an overview of such generic techniques in the three main disciplines of my research: Dynamic programming acceleration, algebraic methods, and data structure design.

The first part of the talk focuses on a method for efficiently computing the min-plus product of totally-monotone matrices. Using this method, I will show how algorithms for planar graph problems such as shortest paths, feasible flow, bipartite perfect matching, and replacement paths can be made much faster than classical algorithms such as Dijkstra and Bellman-Ford.

In the second part of the talk I will describe our dynamic programming (DP) acceleration techniques and how they can be used for speeding up the computation of tree edit-distance, Hidden Markov Model decoding & training, and finding the optimal tree searching strategy (binary search on a tree).