Table of Contents
Cours 2.332.33 Complexity over the RealsResponsable: 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. Motivation and course objectivesThis 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. Pre-requisitesBasic notions from theoretical computer science (Turing machines, NP-completeness, P, NP, etc...) Course DescriptionWe 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? Course LanguageEnglish upon request ⇒ So ENGLISH for 2024. Evaluation 2024
Messages :Messages: * The course stats on Thursday September 19th 2024 * No lecture on October 3 2024 EDITIONDetails to come. But we will cover above mentioned topics, namely: * Computable analysis * Complexity of models from deep learning * Continuous time models of computation VERSION 2024The course will be done on blackboard. Some course notes will be available and put online at the end of each course. * Lecture 1:
* Lecture 2:
* No lecture on Thursday October 3rd !! * Lecture 3:
* Lecture 4:
* Lecture 5:
* Lecture 6:
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)
HISTORICAL PAGES / ARCHIVESBELOW IS THE PAGE OF 2021Warning: the 2024 edition will be different, and will focus on rather different subjects. VERSION 2021The course will be done on blackboard. Some course notes will be available and put online at the end of each course. * Lecture 1:
* Lecture 2:
* Lecture 3:
* Lecture 4:
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:
* Lecture 6:
* Lecture 7:
Notes: part II (updated)
* Lecture 8:
+ 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. BELOW IS THE PAGE OF 2018Course content in 2018 (2021 will be different) :The course will be done on blackboard. Some course notes will be available and put online at the end of each course. * Lecture 1:
* Lecture 2:
* Lecture 3:
* Lecture 4:
* Lecture 5:
* Lecture 6:
* Lecture 7:
* Lecture 8:
Course notes :Course notes: See course above. Bibliography (Edition 2018-2019) :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. Relevant Courses (version 2018)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 |