Space and Time Efficient Structural Improvements of Dynamic Programming
Algorithms
Jesper Nederlof

The subject of this talk is a NWO-project studying the Dynamic Programming
paradigm. The main question here is to perform the following task as
efficient as possible, in terms of space and time: Given a
recurrence, determine one of its specific values. We will first
survey a number of previous results. Most importantly, by applying
transformations, for many recurrences the above task can be performed
in space-efficient manner. This is in strong contrast with more naive
methods where all values of the recurrence need to be stored. Then we
will discuss further research directions on this subject.  The talk will
be self-contained, but familiarity with dynamic programming and standard
NP-complete problems will be helpful to fully appreciate the talk.