Formal Languages, Computability, and Complexity
Lecturers: Michel Abdalla (email@example.com) & Pooya Farshim (firstname.lastname@example.org)
Teaching Assistant: Louis Jachiet (email@example.com)
Lectures: Thursdays 13:15-15:00 at Amphi Rataud. Except 19/10 and 11/01 at Salle 235 B, 29 rue d’Ulm.
Classes/TD: After each lecture from 15:15-17:00 (15 min break)
Other Dates: Mid-term on 16/11. Final exam on 25/01. Project reports due on 11/01.
Pooya’s lectures will be in English. You will have a choice of languages with Michel. The classes by Louis will be in French, unless you decide to switch. An outline of the course contents is given below. Around early December, you will need to decide on a project topic. A preliminary list of possible topics is given below and you are welcome to suggest topics of your own choice. Either the project presentation or the project report should be in English.
- Michael Sipser. Introduction to the Theory of Computation (A nice, gentle introduction to the topics of the course).
- John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (mainly for Automata Theory and Computability).
- Sanjeev Arora and Boaz Barak. Complexity Theory: A Modern Approach (mainly for Complexity Theory).
- Olivier Carton. Langages formels – Calculabilité et complexité (main French textbook).
- Pierre Wolper. Introduction à la calculabilité (a gentler French textbook).
- Scott Aaronson. Quantum Computing since Democritus (nice bedside reading).
Exercise Sheets: See here.
- Lecture 01 (28/09): Course outline. Deterministic and non-deterministic finite automaton. Equivalence of DFAs and NFAs.
- Lecture 02 (05/09): Regular expressions and equivalence with NFAs. Closure properties.
- Lecture 03 (12/10): The pumping lemma. Minimization of DFAs.
- Lecture 04 (19/10): Context-free grammars. Derivations and parse trees. Ambiguity. Chomsky normal form.
- Lecture 05 (26/10): Closure properties of CFLs. Pushdown automata and equivalence with CFGs. Pumping Lemma for CFLs.
- Vacances Toussaint (02/11)
- Lecture 06 (09/11): Turing machines. The Church-Turing thesis. Universal TMs.
- Lecture 07 (16/11): The halting problem and other undecidable problems. Rice’s theorem.
- Lecture 08 (16/11): Post correspondence problem. Decision properties of regular and context-free languages. Undecidability of logical theories.
- Mid-term exam (23/11)
- Lecture 09 (30/11): Time complexity: P, NP, and coNP. NP-completeness.
- Lecture 10 (07/12): NP-completeness of SAT. Other complete problems.
- Lecture 11 (14/12): Space complexity. Savitch’s theorem. PSPACE-completeness. Classes L and NL, co-NL. NL=coNL.
- Lecture 12 (21/12): Circuit complexity. Randomized algorithms. Classes BPP, RP, coRP, and ZPP. BPP in P/poly.
- Lecture 13 (11/01): Cryptography. One-way functions. Pseudorandom generators. The Goldreich-Levin theorem.
- Presentations 18/01 & 19/01: Reports are due 1 week before on 11/01. There will be a doodle page to decide on time slots for the presentations.
- Final exam (25/01): Room W (3 Hours)
See timetable here.
Email me if you’d like to propose your own topic(s).
- Repetition-Free Sequences
- Moore and Mealy Machines
- Other Algorithms for DFA Minimization
- Deterministic Context-Free Languages
- Context-Sensitive Languages
- Greibach Normal Form
- Parikh’s Theorem
- The CYK Algorithm
- Tree Automata
- WSkS and Monadic Logics
- Infinite Automata
- Cellular Automaton
- Recursive Functions
- Random-Access Machines
- Lambda Calculus
- Fast-Growing Functions
- Kolmogorov complexity
- The Arithmetic Hierarchy
- Presburger Arithmetic
- Undecidability of the Generalized 3x + 1 Problem
- Undecidability of Tilings of the Plane
- The Unexpected Examination Paradox
- Gödel’s Incompleteness Theorems
- Topics in Kolmogorov Complexity
- Turing Degrees
- Blum’s Speedup Theorem
- Ladner’s Theorem
- Complexity of Decision versus Search
- The Polynomial Hierarchy
- Barrington’s Theorem
- Class #P
- Complexity of Games
- Parity Is Not in AC0
- Relativization and Natural Proofs Barrier
- Communication Complexity
- PAC Learning
- Learning and Languages
- Hardness Amplification
- Pseudorandom Functions
- Zero-Knowledge Protocols
- Quantum Computation
- Average-Case Complexity
- The (Other) PCP Theorem
Previous year’s web pages.