Responsable: Olivier Bournez, Professeur Ecole polytechnique, bournez@lix.polytechnique.fr, https://www.lix.polytechnique.fr/Labo/Olivier.Bournez

Thursday, from 8:45>11:45

Room 1004.

This course discusses computation (computability and complexity) theory for computations over real numbers.

This is a classical complexity and computability course but applied to questions about real numbers or functions over the numbers. It covers also models based on circuits, or algebraic models.

Basic notions from theoretical computer science (Turing machines, NP-completeness, P, NP, etc...)

We will introduce various ways to model and study complexity of algorithms over the real numbers:

For example:

* Computable analysis: a real is seen as a sequence of converging rational numbers, and one considers Turing machines transforming rational sequences into rational sequences

* Complexity of models from deep learning: deep learning (a.k.a neural network) models are particular models of computation dealing with real numbers. How can we measure the associated complexity?

* Continuous time models of computation: what can be computed using analog electronics, or circuits?

English upon request ⇒ So ENGLISH for 2024.

• a homework assignment serving as midterm exam : HOMEWORK AVAILABLE HERE. Elements of correction here
• a final written exam: ON THURSDAY NOVEMBER 28th 2024 (MORNING, USUAL TIME OF THE LECTURE) (all documents authorized)

Messages:

* The course stats on Thursday September 19th 2024 * No lecture on October 3

Details to come.

But we will cover above mentioned topics, namely:

* Computable analysis

* Complexity of models from deep learning

* Continuous time models of computation

The course will be done on blackboard.

Some course notes will be available and put online at the end of each course.

* Lecture 1:

• Introduction, motivation, tentative of a demo on a THAT.
• Computable analysis: computable reals, Type 2 Turing Machine, notation, representation, computable function
• computable implies continuous

* Lecture 2:

• Intermediate value theorem: various computable/uncomputable statements.
• Computability vs Continuity.

* No lecture on Thursday October 3rd !!

* Lecture 3:

• Computability vs Continuity (continued).
• Alternative characterizations of computable functions.
• Statement of some selected results from computability.
• Myhill's theorem and its proof.

* Lecture 4:

• Complexity in computable analysis: the approach of Ker I Ko's book.
• Selected results

* Lecture 5:

• Complexity of operators in computable analysis: some basic problems
• Complexity of operators in computable analysis: the approach of Kawamura & Cook

* Lecture 6:

• Complexity of operators in computable analysis: some examples of applications

Here are the lecture notes for the computable analysis part: up to this point.

Related lecture notes (updated, relative to Lecture 1 to Lecture 6)

• Computing over an arbitrary structure. The BSS model.

* Lecture 7:

• The complexity class \exists R (also known as ETR)
• Example of \exists R-complete problems

(updated, relative to Lecture 6 to Lecture 7)

• Total search problems. TFNP, FNP, completeness
• The class PPAD
• The complexity of Gradient Descent problems.

* Lecture 8:

• The complexity of Gradient Descent problems (continued).

(updated, Related lecture notes for lecture 7 & 8)

• Continuous time models of computation. The GPAC

Related lecture notes

• Complements:

1. A course given at Ecole Jeunes Chercheuses/Chercheurs Informatique Mathématiques: course notes in French
2. (Rough) English translation of these course notes Related lecture notes

Warning: the 2024 edition will be different, and will focus on rather different subjects.

The course will be done on blackboard.

Some course notes will be available and put online at the end of each course.

* Lecture 1:

• Introduction, motivation du cours
• Computable analysis: computable reals. (see consolidated pdf below)
• Course notes: Chapter 3 of pdf below.

* Lecture 2:

• Computable analysis: computable functions (see consolidated pdf below)
• Course notes: Chapter 4 and 5 of pdf below.

* Lecture 3:

• Computable analysis: representing spaces of functions, subsets. Intermediate value theorem (see consolidated pdf below)
• Course notes: Chapter 6 and 7, 8 of pdf below.

* Lecture 4:

• Computable analysis: Intermediate value theorem. Complexity. Some selected results
• Course notes: Chapter 8, 9 and 10 of pdf below.

part I (not available any more)

Bibliography for 4 first courses:

* Klaus Weihrauch. Computable Analysis: an introduction. Springer. 2000.

* http://cca-net.de/vasco/, an the excellent “Tutorial: Computability & Complexity in Analysis” on this web page.

* Vasco Brattka, Peter Hertling, and Klaus Weihrauch. A tutorial on computable analysis. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable, pages 425-491. Springer, New York, 2008.

* Lecture 5:

• Static indecidability. Example of Richardson Theorem
• Dynamic undecidability. Computing with PCD and PAM

* Lecture 6:

• The General Purpose Analog Computer (GPAC)
• GPAC-generable functions and closure properties
• Simulating a Turing Machine with GPAC-generable functions in discrete time

* Lecture 7:

• Simulating a Turing Machine with GPAC-generable functions in continuous time.

Notes: part II (updated)

• Complexity and GPAC: polynomial time corresponds to length, up to polynomial time.

Polynomial Time Corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length

• Computing over a structure: the basic model, circuits, and definition of complexity classes based on circuits. (see notes below)

* Lecture 8:

• Computing over a structure: P, NP, NP-completeness, relations with discrete complexity. See notes below + articles of Koiran below.

+ Bibliography:

- Blum, L., BLUM, L. A., Cucker, F., Shub, M., & Smale, S. (1998). Complexity and real computation. Springer Science & Business Media.
- Poizat, B. (1995). Les petits cailloux (Vol. 995). Lyon: Aléas.
- Koiran, P. (1994). Computing over the reals with addition and order. Theoretical Computer Science, 133(1), 35-47.
- Koiran, P. (1997). A weak version of the Blum, Shub, and Smale model. Journal of Computer and System Sciences, 54(1), 177-189.

part III

The course will be done on blackboard.

Some course notes will be available and put online at the end of each course.

* Lecture 1:

• Introduction
• Computable analysis: computable reals. (see consolidated pdf below)

* Lecture 2:

• Computable analysis: computable functions (see consolidated pdf below)

* Lecture 3:

• Computable functions: oracle view. Modulus of continuity.
• Computable subsets.

* Lecture 4:

• Intermediate Value Theorem
• Complexity

* Lecture 5:

• Selected results
• Complexity

* Lecture 6:

• Complexity (end)
  • Consolidated pdf: courses 1-6 |Computable analysis (not available any more)

* Lecture 7:

• Computing with dynamical systems with non-necessarily rationals coefficients
• Space/time contractions for PCD Systems

• Dynamic undecidability

• The General Purpose Analog Computer / Differential Analysers

* Lecture 8:

• * The General Purpose Analog Computer: Stability Properties of generable functions
• The General Purpose Analog Computer: Computability Properties
• (cf Dynamic undecidability also for computability properties)

Course notes:

See course above.

Bibliography for first courses:

* Klaus Weihrauch. Computable Analysis: an introduction. Springer. 2000.

* http://cca-net.de/vasco/, et l'excellent “Tutorial: Computability & Complexity in Analysis” sur cette page.

* Vasco Brattka, Peter Hertling, and Klaus Weihrauch. A tutorial on computable analysis. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable, pages 425-491. Springer, New York, 2008.

The following is a coherent list of courses on the thematic 'Algorithms and Complexity'.

* 2-11-1 Advanced Algorithms * 2-11-2 Randomness in Complexity * 2-12-1 Techniques in Cryptography and Cryptanalysis * 2-13-2 Error correcting codes and applications to cryptography * 2-18-1 Distributed algorithms for the networks * 2-18-2 Algorithmique distribuée avec mémoire partagée * 2-24-1 Optimisation * 2-29-1 Graph algorithms * 2-33-1 Theory of Computations * 2-34-1 Quantum information and applications * 2-38-1 Algorithms for embedded graphs