This is an old revision of the document!


Computer Science of 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.

Administration:

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

Synopsis

0. Introduction & Motivation (pdf,ppt:
“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 Theory of Computation (pdf,ppt:
Un-/Computability, Halting Problem, Semi-/Decidability, Reduction, WHILE model of computation, SMN property/Currying, Oracle computation
II. 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
III. 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'
IV. 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
V. Imperative programming over the Reals:
Semantics of tests Example: Gaussian Elimination Verification in Floyd-Hoare Logic Practical implementation in iRRAM
VI. 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 2nd-order polynomial complexity theory Weihrauch reductions

Test questions for self-assessment

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

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