Formal Languages, Computability, and Complexity

Lecturers: Michel Abdalla (michel.abdalla@ens.fr) & Pooya Farshim (pooya.farshim@ens.fr)
Teaching Assistant: Louis Jachiet (louis.jachiet@ens.fr)
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 15/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. 

References

Exercise Sheets: See here.  

Lecture Notes: Notes for regular and context-free languages.

Contents

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

Presentation Topics

Email me if you’d like to propose your own topic(s). 

  1. Repetition-Free Sequences
  2. Moore and Mealy Machines
  3. Other Algorithms for DFA Minimization
  4. Deterministic Context-Free Languages
  5. Context-Sensitive Languages
  6. Greibach Normal Form
  7. Parikh’s Theorem
  8. The CYK Algorithm
  9. Tree Automata
  10. WSkS and Monadic Logics
  11. Infinite Automata
  12. Cellular Automaton
  13. Recursive Functions
  14. Random-Access Machines
  15. Lambda Calculus
  16. Fast-Growing Functions 
  17. Kolmogorov complexity
  18. The Arithmetic Hierarchy
  19. Presburger Arithmetic
  20. Undecidability of the Generalized 3+ 1 Problem
  21. Undecidability of Tilings of the Plane
  22. The Unexpected Examination Paradox
  23. Gödel’s Incompleteness Theorems
  24. Topics in Kolmogorov Complexity
  25. Turing Degrees
  26. Blum’s Speedup Theorem
  27. Ladner’s Theorem
  28. Complexity of Decision versus Search
  29. The Polynomial Hierarchy
  30. Barrington’s Theorem
  31. Class #P
  32. IP=PSPACE
  33. Complexity of Games
  34. Parity Is Not in AC0
  35. Relativization and Natural Proofs Barrier
  36. Communication Complexity
  37. PAC Learning
  38. Learning and Languages
  39. Evolvability
  40. Hardness Amplification
  41. Pseudorandom Functions
  42. Zero-Knowledge Protocols
  43. Quantum Computation
  44. Average-Case Complexity
  45. The (Other) PCP Theorem

Previous year’s web pages.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

.

Advertisements