Algorithmic Foundations of Numerics (CS700/MAS583) in Fall 2016 at KAIST

This lecture applies to, and investigates from the perspective of, the classical (i.e. discrete) Theory of Computation, problems usually pertaining to numerics;
that is, over continuous universes like real numbers, vectors, converging sequences, continuous/smooth/integrable functions, compact Euclidean subsets -- and more generally separable metric spaces.
One particular highlight is the proof of Harvey Friedman's and Ker-I Ko's celebrated connection between smooth maximization/integration and P-vs-NP-vs-#P;
and our extensions similarly characterizing famous complexity-theoretic conjectures in terms of numerical problems such as solving ODEs and Poisson's Equation as well as the phase transition from smooth to analytic via Gevrey's Hierarchy.
Another one is our characterization of Kolmogorov's entropy in terms of relative bit-complexity of the space's metric.
On the practical side we will actually implement some of the reliable algorithms using a C++ library that overloads usual arithmetic to support a new encapsulated data type REAL but with (unavoidably and subtly) modified semantics of tests.


Instructor: Martin Ziegler

Lectures: room #3445 in building E3-1 (School of Computing)

Schedule: Tuesdays and Thursdays 2:35pm to 3:50pm

Language: English

Teaching Assistant: 박지원

Office hours: to be announced

Attendance: 10 points for missing less than 5 lectures, 9 when missing 5 lectures, 8 when missing 6, and so on: 14 or more missed lectures earn no attendance points.

Grading: The final grade will be composed as follows:
Attendance 10%, Assignments 15%, Presentation 15%, Midterm exam 30%, Final exam 30%.

Midterm exam (written) on October 20 (Thursday) 13h30 to 15h30
Final exam on December 15 (Thursday) 13h00 to 14h00 (written, 50%) + 14h30 to 16h30 (individual oral, 50%)
Presentation of assignments in class, individually on selected dates.



  1. Recap on discrete Theory of Computation:
  2. Computability theory over the Reals:
  3. Computability on separable metric spaces:
  4. Complexity theory over the Reals:
  5. Imperative programming over the Reals:
  6. Uniform complexity of operators in Analysis:



Questionaire for Recap/Self Evaluation:

Which of the following operations preserve polynomial-time/computability and why/not?


Selected References: