10/6/2005
3:30pm-4:30pm
ECCR 265
|
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.
|
The Department holds colloquia throughout the Fall and Spring semesters. These
colloquia, open to the public, are typically held on Thursday afternoons, but
sometimes occur at other times as well.
If you would like to receive email notification of upcoming colloquia,
subscribe to our
Colloquia Mailing List.
If you would like to schedule a colloquium, see
Colloquium Scheduling.
Sign language interpreters are available upon request. Please contact
Stephanie Morris at least five days prior to the colloquium.
|
