home · mobile · calendar · colloquia · 2005-2006 · 

Colloquium - Rajopadhye

Simplifying Reductions
Colorado State University

We present a technique to reduce the computational complexity of the algorithm embodied in a program. Our technique, which can be automated to be used in a compiler, works for a class of programs called affine control loops, or equivalently, equational programs over polyhedral domains. The method is optimal in the sense that the final program has the smallest possible polynomial complexity. We have used it to derive an O(n3) program from an O(n4) formulation of an algorithm that arises in RNA folding. Researchers in the field took over 8 years to discover the improved algorithm. This is joint work with PhD student Gautam Gupta.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:13)