Computational Complexity in Analysis: A lecture held by Martin Ziegler in spring 2015 at TU Darmstadt

This lecture applies the classical (i.e. discrete) theory of computation to problems usually pertaining to numerics, that is, over continuous universes such as real numbers, vectors, sequences, functions, subsets, and more generally separable metric spaces. As one particular highlight we learn the proof of Harvey Friedman's Ker-I Ko's celebrated connection between smooth maximization/integration and P-vs-NP-vs-#P; on the practical side we will actually implement some of the reliable algorithms in unbounded precision and compare their performance to the theoretical predictions.



  1. Recap on discrete complexity:
  2. Real Complexity Theory:
  3. Uniform Complexity of Operators

Homework/assignments/problems for the weekly tutorial classes:

01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12.


Selected References: