Fall 2026 · CUHK-Shenzhen
| Lectures | MW 8:30 to 9:50 in Administration Building E206 |
|---|---|
| Tutorial | Tue 19:00 to 19:50 in Teaching D, Room 307 |
| Instructor |
Aditi Dudeja Email: aditidudeja@cuhk.edu.cn Office hours: Monday, Tuesday: 4pm - 5pm in DY 504b and Wednesday, Thursday: 4pm - 5pm online (on Zoom ) |
| Teaching Assistant |
ZHU Tianran Email: tianranzhu@link.cuhk.edu.cn Office hours: Monday: 4-5pm in Zhi Xin Building, Room 408, Seat 49 (ZX 408-49) and Wednesday: 4-5pm online (on Zoom ) |
| USTF |
SUN Youran Email: youransun@link.cuhk.edu.cn Office hours: Monday, Thursday: 1-2pm online (on Zoom ) |
| Expected background |
Official pre-requisite is CSC3001. Official co-requisite is
CSC4120. If you don't satisfy these requirements, but are comfortable with proofs and want to enroll, please email the instructor. |
| Textbook |
Introduction to the Theory of Computing, 3rd Edition by
Michael Sipser. ISBN-13: 9780357670583. The book is on reserve in the CUHK-Shenzhen Library. |
| Course outline |
Official course description
. Syllabus A lecture-by-lecture guideline is given below. |
| Communication | For course-related emails, please begin the subject line with [CSC4010]. |
The question of which tasks can be performed efficiently is central to human experience, since time and other resources are always in shortage. The field of theoretical computer science studies the effects of limited resources: How does restricting the time, memory, and other resources available to algorithms affect their ability to perform tasks? This question is formulated and studied as generally as possible and with mathematical rigor, using well-defined abstract notions of algorithms, tasks, and resources.
This course teaches how to mathematically model general computation and how to analyse models. The main conceptual focus of the course is impossibility results (i.e. lower bounds), which rigorously prove limits for models of computation. A secondary focus is utilizing impossibility results for productive purposes, i.e. building algorithms and protocols from lower bounds. The key points students can take from the course are:
The course will have four (planned) modules. The following list is tentative and may be updated as the semester progresses.
| Computability Theory | In this module, we will learn how to mathematically model computational problems and models. We will study Turing machines, which are arguably, the right model to capture computation. We will ask which problems are computable by a Turing Machine given an arbitrarily large (but finite) number of resources. We will show certain problems are uncomputable. An example of such a problem is the Halting Problem. |
|---|---|
| Complexity Theory | The distinction between “computable” and “uncomputable” problems is crude, and provides only limited information as to which problems can actually be computed, because it does not take into account resource limitations. Specifically, even computable problems may be beyond reach of any real-world computational procedure, whose resources are inherently limited. In this model, we will obtain more information about realistically solvable problems by analyzing resource-bounded models. The resources we will focus on are time and memory. We will show (among other things) that given more time, a Turing machine can solve more problems. |
| Fine-grained Complexity | This area of research attempts to discover the precise time complexity of solving specific interesting problems. For example, given a set of vectors, can we find a pair of orthogonal vectors faster than brute-force? |
| Cryptographic Applications of Lower Bounds | In this module, we will learn that the lower bounds we have proved so far are useful in practice and can be leveraged to build algorithms and cryptographic protocols for safe computation. |
The course evaluation will use proof-based in-class tests, a midterm examination, and a final examination. There will be 4 in-class tests, and the test with the lowest score will be dropped. Tests will be based on periodic assignments, which won't be evaluated but you're encouraged to discuss your solutions in office hours and in tutorials. The dates below are tentative and may be adjusted with advance notice.
| In-class tests (based on assignments) | 40% |
|---|---|
| Test dates: 29/9/26, 27/10/26, 24/11/26, 15/12/26 | |
| Midterm examination | 30% |
| Midterm date: 2/11/26 | |
| Final examination | 30% |
| Final-exam date: TBA | |
The calendar is tentative. Dates, lecture materials, assignment releases, and assessment information will be added as the term progresses.
| # | Date | Topic | References | Problem Sets |
|---|---|---|---|---|
| L1 | 7/9 | Course Outline and Introduction |
Lecture 1
Sipser: Chapter 0, and Pages 202-204 |
|
| T1 | 8/9 | Countability and Uncountability | Tutorial 1 | |
| L2 | 9/9 | Computational Problems as Languages |
Lecture 2
Lecture 2 (annotated) AB09: Sections 1.1.1-1.1.2, Aspnes: Chapter 2 |
Problem Set 1 (Questions 1-3 under Section 1) Tutorial 2 |
| L3 | 14/9 | Turing Machines as Algorithms; Decidable Languages; Recognizable Languages | Lecture 3
Lecture 3 (Annotated) Reading: Section 3.1 of Sipser |
|
| L4 | 16/9 | Formal Definition of Turing Machines; More Decidable and Recognizable Languages; Properties of Decidable/Recognizable Languages | Lecture 4
Lecture 4 (annotated) |
Problem Set 1 (Questions 1-2 under Section 2) |
| L5 | 21/9 | Church-Turing Thesis: Motivation via variants of TMs, Statement of Church-Turing Thesis | Lecture 5 Lecture 5 (Annotated) Reading: Sections 3.2 and 3.3 of Sipser (skip the part about nondeterministic TMs) |
|
| L6 | 23/9 | Continuation of Multitape TMs, Universal Turing Machines | Lecture 6
Lecture 6 (annotated) Reading: Section 3.1.6 of Aspnes for UTMs |
Problem Set 2 |
| L7 | 28/9 | Undecidablity/Unrecognizability using Diagonalization | Lecture 7 Reading: Section 4.2 of Sipser |
|
| L8 | 30/9 | Proving Undecidability/Unrecognizability via Reductions I | ||
| L9 | 12/10 | Undecidability/Unrecognizability via Reductions II | ||
| L10 | 14/10 | Asymptotic Notation Refresher, Time Complexity | ||
| L11 | 19/10 | Time Hierarchy Theorem | ||
| L12 | 21/10 | P and NP | ||
| L13 | 26/10 | Boolean Formulas and Satisfiability | ||
| L14 | 28/10 | Cook-Levin Theorem: SAT is NP-Complete | ||
| L15 | 2/11 | Midterm | ||
| L16 | 4/11 | Space Complexity | ||
| L17 | 9/11 | Time-Space Hierarchy | ||
| L18 | 11/11 | Savitch's Theorem | ||
| L19 | 16/11 | Logarithmic Space | ||
| L20 | 18/11 | Sublogarithmic Space | ||
| L21 | 23/11 | Constant Space Computation | ||
| L22 | 25/11 | Fine-grained complexity I | ||
| L23 | 30/11 | Fine-grained complexity II | ||
| L24 | 2/12 | Fine-grained complexity III | ||
| L25 | 7/12 | Using Lowerbounds for Cryptography I | ||
| L26 | 9/12 | Cryptographic applications of lower bounds II | ||
| L27 | 14/12 | Cryptographic applications of lower bounds III | ||
| L28 | 16/12 | Review |
The main textbook for the course is Introduction to the Theory of Computing, 3rd Edition by Michael Sipser. ISBN-13: 9780357670583
There are other resources you may consult, in case you are curious. We will add pointers to specific chapters in the course calendar.
| Wat26 | Thomas Watson, Complexity in Computer Science . |
|---|---|
| B | Boaz Barak, Introduction to Theoretical Computer Science (freely available online). |
| AB09 | Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach . |
| Vio26 | Emanuel Viola, Mathematics of The Impossible . |
This short list collects some foundational references connected to the lectures. It will be expanded during the term.
Here are several courses with closely related material and useful lecture notes or slides:
Last updated: September 3, 2026.