Limits of dynamic programming

• Applicant: Professor Dr. Georg Schnitger
• Subject Area: Theoretical Computer Science
• Term: from 2013 to 2017
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 237501959

Our current knowledge of the dynamic programming complexity (DP complexity) of algorithmic problems is very disappointing, since the all-pairs shortest path problem is one of only few nontrivial algorithmic problems whose DP complexity is reasonably understood. The DP complexity of other shortest path problems remains unresolved as well the alleged optimality of the many fundamental dynamic programming algorithms in computer science and bioinformatics. We encounter the same bleak situation when approximating with dynamic programming algorithms.Our goal is to formulate adequate models capturing the paradigm of dynamic programming, and to prove lower bounds for important optimization problems in these models. In particular, powerful methods from boolean circuitcomplexity and communication complexity are to be modified to work also fordynamic programming algorithms.

• DFG Programme: Research Grants