Pooya Farshim

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

References

• 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 Notes:

• Regular and context-free languages.
• Computability.

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): Room W (3 Hours)

Presentation Topics

See timetable here. 

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 3x + 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.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

.