Daniel Roche
Department of Computer Science
United States Naval Academy
3:30 PM
154 Hurley
Pattern Matching, X+Y, and Sparse Multiplication
The pattern matching problem is about finding a search pattern (possibly with wildcard characters) within a larger text, and has applications ranging from music retrieval to genetics. The X+Y problem is a basic algorithmic puzzle: given two sets of integers X and Y, find all sums (x+y) between the elements of the two sets. Finally, sparse polynomial multiplication is the problem of determining the product of two multivariate polynomials, where only the nonzero terms of the input and output are explicitly stored.
On the surface, these problems are entirely unrelated. But they all share an important similarity from a computational point of view: in the worst case, they require quadratic running time, but in many cases the size of the output is significantly less than the worst-case bound suggests. This happens because of overlapping matches in pattern matching, repeated sums in X+Y, or colliding terms in polynomial multiplication. So it is reasonable to seek output-sensitive algorithms, whose running time decreases when the output size is small.
As it turns out, the core to solving all three problems comes from recent advances in sparse polynomial interpolation, that is, discovering a formula for an unknown polynomial after sampling it at a small number of chosen points. We will outline the connection between each of these important problems and sparse interpolation, and present a randomized algorithm to compute the answer to all three in “nearly linear” expected running time.
This is joint work with Andrew Arnold at the University of Waterloo.
Full List of Applied Math Seminar Speakers
