Computer Science for Continuous Data: Algorithmic Foundations of Numerics (CS700)

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 #113 in building N1 online (Zoom)
Schedule: Tuesdays and Thursdays 2:30pm to 3:45pm
Language: English (only)
Final exam: Dec.14~18, take-home

0. Introduction & Motivation (pdf,ppt,video):
“Virtues” of Computer Science and Mathematics, Abstract Data Types / Structures in Computer Science and Mathematics, IEEE 754 / Floatingpoint Discretization Properties and Reliability, Numerical Folklore and Myths
I. Recap on Discrete Computability Theory (pdf,ppt,video1,video2):
Un-/Computability, Halting Problem, Semi-/Decidability, Reduction, WHILE model of computation, SMN property/Currying, Oracle computation, Limit Lemma, Arithmetic Hierarchy
II. Computability theory over the Reals (pdf,ppt,video):
a) Computing Real Numbers: three equivalent notions, counter/examples, oracle-computable reals/limit Lemma (video)
b) Computing Real Sequences: semi-decidability / strong undecidability of equality, no computable sequence contains all computable reals (video)
c) Computing Real Functions: closure under composition and restriction and sequences, necessarily continuous, computable Weierstrass Theorem (video)
d+e) Un/Computability over Real Functions: un/computable Argmin/Root Finding, un/computable Derivative, un/computable, un/computable Wave Equation (video1, video2)
f) Multi-Functions & Enrichment: generalized restriction, fundamental theorem of algebra, fuzzy sign, Archimedian property, linear algebra, analytic functions (video)
g) Computing Real Operators: encoding continuous functions, uniform computability, encoding compact subsets, Boolean set operations (video)
III. Computability on Topological Spaces (pdf,ppt):
a) Basic Spaces: Cantor/Baire, Computing, Cost, Continuity, Compactness (video)
b) Representations: Definition, Real Examples revisited, Continuity and Compactness revisited, Realizers of Multi/functions between Represented Spaces, Reduction between Representations, Admissible/Standard Representations, Main Theorem, Sequence Representation (video1,video2)
IV. Recap on Discrete Complexity Theory (pdf,ppt)
a) Computation with cost, selected complexity classes, classifying example decision problems, comparing decision problems, complexity class picture (video)
b) complexity class picture, counting complexity class #P, unary complexity classes, parameterized complexity, average-case complexity, various reductions, between functions (video)
V. Complexity theory over the Reals (pdf,video):
a) Polytime-computable real numbers, polytime-computable real functions, quantitative computability ⇒ quantitative continuity, operations that preserve polytime computability (video)
b) (Strongly) polytime-computable real sequences, polytime analytic function ⇔ polytime Taylor coefficients, operations on polytime analytic functions (video)
c) Maximizing polytime functions “in NP”, indefinite Riemann integration “in #P”, definite Riemann integration “in #P₁”, ODESOLVE “in PSPACE” (video)
d) Numerical characterizations of Discrete complexity classes: Parametric maximization is NP-“complete”, in/definite Riemann integration is #P/#P₁-“complete”, (smooth) ODEs are PSPACE-“complete” (video)
e) Intrinsic Complexity of PDEs: Poisson and Heat Equation (video)
VI. Complexity on Metric Spaces
a) Complexity of points, complexity of functions, complexity and quantitative continuity, polynomial admissibility, polynomial 'Main Theorem', entropy as quantitative compactness (pdf,ppt,video)
b) Quantitative coding theory of compact metric spaces (pdf,ppt,video1,video2,video3)
VII. Imperative programming over the Reals (pdf,ppt,video):
WHILE Programs over N,R,K=Kleene, non-extensional integer rounding naive and fast, exponential function, trisection for simple root finding, matrix determinant with multival.pivoting, Turing-completeness over the Reals
VIII. Reduction between Continuous Problems (pdf,ppt,video):
Computing integer functionALs/operators, generalized polynomial resource bounds, degree of 2nd-order polynomials
Summary (pdf,ppt,video)

Mathematical background:

• What does it mean for a sequence to converge?
• What does it mean for a function to be continuous?
• What does it mean for a set to be compact?
• Why is every continuous function on a compact domain uniformly continuous?

Computer science background:

• C++/Linux
• Asymptotic Landau calculus
• P/NP

• 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).