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.

Synopsis:

Recap on discrete Theory of Computation:
- un-/computability, Halting Problem
- asymptotic runtime and memory
- machine models: unit-cost vs. bit-cost
- complexity classes LOGSPACE, P, NP₁, NP, #P, PSPACE, EXP
- reductions and completeness, parameterized complexity
- oracle computation
Computability theory over the Reals:
- real numbers: binary vs. approximation
- sequences, limits, rate of convergence
- qualitative stability: computability and continuity
- real arithmetic, join, maximum, integral
- root finding, argmax, derivative
- uncomputable wave equation
- analytic functions, discrete enrichment
- multivaluedness, computability in linear algebra
Computability on separable metric spaces:
- C[0;1] and computable Weierstrass Theorem
- encoding compact Euclidean subsets
- computability of function image and preimage
- theory of encodings (TTE)
- Main Theorem: continuity = oracle computability
- Henkin-continuity of multivalued 'functions'
Complexity theory over the Reals:
- quantitative stability and polynomial-time computability
- maximizing smooth polynomial-time functions is NP-'complete'
- hardness of integration, of solving ODEs, and of Poisson's PDE
- polynomial-time computable analytic functions
- fixed-parametrized complexity and Gevrey's Hierarchy
- average-case complexity of real functions
Imperative programming over the Reals:
- Semantics of tests
- Example: Gaussian Elimination
- Verification in Floyd-Hoare Logic
- Practical implementation in iRRAM
Uniform complexity of operators in Analysis:
- TTE and computational complexity
- encoding metric spaces of polynomial entropy
- adversary arguments and exponential entropy
- encoding function spaces via oracles
- Lebesgues decomposition and computational complexity
- 2^nd-order polynomial complexity theory
- Weihrauch reductions

E-Teaching:

Slides of Section 0 (PDF), 0 (PPT), I (PDF), I (PPT), II (PDF), II (PPT), (discrete) Complexity Theory, III (PDF), III (PPT),
For programming assignments a virtual linux server has been set up with iRRAM installed; details in the lecture...
Due to a business trip of the instructor, the lecture scheduled for Sept.13 will instead take place on Sept.8 at 16h15 in E6 #1401.
Homework assignment #0 is due on the evening of September 19, 2016 by (preferably PGP signed) email.
Homework assignment #1 is due on the evening of October 5, 2016.
Homework assignment #2 is due on the evening of October 26, 2016.
Homework assignment #3 is due on the evening of November 21, 2016.
Homework assignment #4 is due on the evening of December 12, 2016.

Questionaire for Recap/Self Evaluation:

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

limit (of converging sequence)
limit (of 'fast' converging sequence)
arithmetic (addition, subtraction, multiplication, reciprocal)
integral (of continuous function)
maximum/minimum (of continuous function)
argmax/argmin (of smooth function)
root (of polynomial)
root (of smooth function)
derivative (of continuously differentiable function)
derivative (of twice continuously differentiable function)

Selected References:

Klaus Weihrauch: Computable Analysis: An Introduction, Springer (2000).
Ker-I Ko: Complexity Theory of Real Functions, Birkhäuser (1991).
Mark Braverman, Stephen Cook: Computing over the Reals: Foundations for Scientific Computing, Notices of the AMS (2006).
Akitoshi Kawamura, Stephen Cook: Complexity Theory for Operators in Analysis, ACM Transactions on Computation Theory 4 (2012).
Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick, Martin Ziegler: Computational Complexity of Smooth Differential Equations, Logical Methods in Computer Science (2014).
Akitoshi Kawamura, Norbert Müller, Carsten Rösnick, Martin Ziegler: Computational Benefit of Smoothness: Parameterized Bit-Complexity of Numerical Operators on Analytic Functions and Gevrey's Hierarchy, pp.689-714 in the Journal of Complexity vol.31:5 (2015).
Akitoshi Kawamura, Florian Steinberg, Martin Ziegler: On the Computational Complexity of the Dirichlet Problem for Poisson's Equation, to appear in Mathematical Structures in Computer Science
H.Férée, M.Ziegler: "On the Computational Complexity of Positive Linear Functionals on C[0;1]", pp.489-504 in Proc. 6th Int. Conf. on Mathematical Aspects of Computer and Information Sciences (MACIS 2015), Springer LNCS vol.9582 (2016).
M.Schröder, F.Steinberg, M.Ziegler: "Average-Case Bit-Complexity Theory of Real Functions", pp.505-519 in Proc. 6th Int. Conf. on Mathematical Aspects of Computer and Information Sciences (MACIS 2015), Springer LNCS vol.9582 (2016).
Katrin Tent, Martin Ziegler (Freiburg!): Computable Functions of Reals
A. Kawamura, M. Ziegler: "Invitation to Real Complexity Theory: Algorithmic Foundations to Reliable Numerics with Bit-Costs", 18th Korea-Japan Joint Workshop on Algorithms and Computation (2015).