Contents may differ from the current or most recent offering of the course.
Course Description
An advanced course building on foundational ideas in the theory of computing. Further properties of regular and context-free languages, language classes beyond context-free, parsing, randomness and probabilistic computation, relativized computation, complexity hierarchies, and circuit complexity will be discussed. Prior experience with theory of computing at the undergraduate level is recommended.
See the course outline for more information.
Course Details
Lecture Time/Place
Monday, 12:30pm–1:20pm; Wednesday, 11:30am–12:20pm; Thursday, 1:30pm–2:20pm
All lectures are held in Mulroney Hall, room 4032.
Textbooks
Undergraduate-level review material: M. Sipser, Introduction to the Theory of Computation. Cengage, 3rd edition, 2012.
Graduate-level material: S. Arora and B. Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
The undergraduate-level textbook is available for sale at the campus bookstore. A free electronic copy of a draft edition of the graduate-level textbook is available online. Course notes will also be provided for each lecture.
Marking Scheme
- Two assignments (10% each, total 20%)
- Two quizzes (15% each, total 30%)
- Group lecture (total 30%): a lesson plan (10%) and the lecture itself (20%)
- Individual report on the group lecture (10%)
- Participation (total 10%): class participation (5%) and reviewing group lectures (5%)
You must complete the group lecture and individual report components in order to pass the course. You may not complete one without completing the other.
News
- Mar. 5: Lecture notes for the ninth week have been posted.
- Feb. 27: The second assignment has been posted. It is due by Mar. 13 at 1:30pm.
- Feb. 26: Lecture notes for the seventh week have been posted.
- Feb. 10: Lecture notes for the sixth week have been posted.
- Feb. 6: Information about the group lecture and report has been posted.
- Feb. 5: Lecture notes for the fifth week have been posted.
- Jan. 30: Due to the delayed opening of the university today, Quiz 1 will be postponed. It will now be written on Feb. 3 during our lecture time.
- Jan. 23: The first assignment has been posted. It is due by Feb. 6 at 1:30pm.
- Jan. 20: Lecture notes for the third week have been posted.
- Jan. 13: Lecture notes for the second week have been posted.
- Jan. 8: Lecture notes for the first week have been posted.
- Jan. 6: Welcome to the course! Please see our Moodle page for details about the course this term.
Lectures
| Week | Notes | Readings |
| 1 | Introduction, Turing machines | Arora and Barak, 1.1–1.2 |
| 2 | Foundations of complexity: Running time, work space, speedup, compression | Arora and Barak, 1.3, 1.6 |
| 3 | Foundations of complexity (cont’d): Gap theorem, constructibility, resource bounds | Arora and Barak, 3.1–3.2, 4.1 |
| 4 | Foundations of complexity (cont’d): hierarchy theorems, Savitch’s theorem | Arora and Barak, 4.2 |
| 5 | Time and space complexity | Arora and Barak, 2.1, 2.5–2.7 |
| 6 | Hardness, completeness, and complements | Arora and Barak, 2.2–2.4, 4.3 |
| — | Winter study break | — |
| 7 | Probabilistic computation: Probabilistic TMs, Las Vegas/Monte Carlo algorithms | Arora and Barak, 7.1–7.2 |
| 8 | Probabilistic computation (cont’d): Randomized complexity | Arora and Barak, 7.3–7.5 |
| 9 | Interactive proof systems, zero-knowledge proofs | Arora and Barak, 8.1–8.3, 9.4 |
| 10 | Group lectures | — |
| 11 | Group lectures | — |
| 12 | Group lectures | — |
Assignments
- Assignment 1, due Feb. 6
- Lesson Plan, due Feb. 13
- Assignment 2, due Mar. 13
- Report, due Apr. 3
Assignments are due at the beginning of class on the due date. Late assignments will be accepted up to the beginning of the first class following the due date. Late assignments are subject to a penalty of 10% deducted from the earned mark.
The lesson plan and report must be submitted on the due date. Late submissions will not be accepted.
Quizzes
Quiz 1
Date: Jan. 30 Feb. 3, 2025
Time: 12:30pm–1:20pm
Place: Gilmora Hall, Room 001 (NOT our usual classroom)
Content: All material from Weeks 1 to 4
Quiz 2
Date: Mar. 6, 2025
Time: 1:30pm–2:20pm
Place: Mount Saint Bernard, Room 225 (NOT our usual classroom)
Content: All material from Weeks 5 to 8
Personnel
Instructor
Taylor J. Smith
Email: tjsmith [at] stfx [dot] ca
Office: Annex, Room 9A
Office hours: Monday/Wednesday/Thursday, 10:30am–11:20am, or by appointment