CSCI3360 Introduction to Computational Complexity (2026 Fall)

Course Instructor:

• Prof. Xiao LIANG (xiaoliang [at] cuhk.edu.hk)

Time and Venues: Teaching Assistant:

Important Message for Perspective Students

---

• No programming; all theory: This course is purely theoretical. It does not involve programming, real-world implementation, or software engineering considerations.
• Difficulty level: The course assumes that students have basic undergraduate-level mathematical maturity. In particular, it relies on probability theory as a foundational tool. You can expect a difficulty level and workload comparable to those of CSCI3160 Design and Analysis of Algorithms.

Grading Scheme

---

• Quizzes (20%): There will be two quizzes, each accounting for 10%. The quiz times will be announced one week in advance.
• Midterm (46%): There will be one midterm exam. Although it's called a "midterm," it will actually take place in the later weeks of the course (e.g., between Week 11 and Week 13). The exact time of the midterm will be announced at least two weeks in advance. This scheduling ensures that the exam occurs after most of the course material has been covered. It also compensates for the fact that this course does not have a (centralized) final exam!
• Group Homework (14%): There will be two problem sets, each worth 7%. Students are allowed to form groups and submit one joint solution. More details will be announced later.
• Group Project (20%): Students will work in groups to choose a complexity-theory paper published at a reputable conference (e.g., STOC/FOCS/SODA/ICALP), write a report, and give a presentation. More details will be provided in due course.

Textbooks

---

All-in-one lecture notes: This document contains all the notes used for our lectures. Most of the teaching in this course will not use slides; instead, the instructor will use the whiteboard. This is a common practice in mathematical or theoretical courses, as it better demonstrates derivations, calculations, and proofs. To help students grasp the material and have a reference for review, we provide these all-in-one lecture notes. This document will be updated periodically as the course progresses. Slides used for tutorials are provided as hyperlinks in the weekly schedule below.

The following are some useful supplementary materials. They are optional.

• [AB] – Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak
• [DPV] – Algorithms, by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani.

Additional Information

---

Course Description: This course provides an introduction to the field of computational complexity, a cornerstone of computer science that studies the inherent difficulty of computational problems and classifies them according to their computational resources, such as time and space. The course is designed to elucidate the pivotal role of computational complexity in shaping the landscape of modern computing, with emphasis on its connections to algorithm design and related areas. Students will gain a broad view of how complexity theory informs and is informed by other scientific and technological domains. Interdisciplinary connections to artificial intelligence, cryptography, and quantum computing may also be covered if time permits; these topics are optional and will depend on this year's teaching progress and the students' learning pace.

Tentative topics:

• Resources for computation (time, space, nondeterminism, randomness) and their associated complexity classes
• Relationships among resources (P vs NP and more), reductions, and completeness
• Space complexity: PSPACE, L, NL
• Randomized computation: RP, BPP
• Basic circuit complexity (P/poly, NC, and more)
• Counting: #P, Toda's Theorem, approximate counting
• (If time permits:) Alternation: the polynomial hierarchy, time-space trade-offs for SAT
• (If time permits:) Interactive proofs (AM, MA, IP)
• (If time permits:) Probabilistically checkable proofs (PCP) and non-approximability
• (If time permits:) Large Language Model vs Complexity Theory: the use of LLMs for theorem proving, proof verification, and complexity-theoretic implications of LLMs
• (If time permits:) average-case complexity and connections to cryptography, including TFNP, Kolmogorov complexity, one-way functions, factoring, discrete logarithm, and Diffie-Hellman
• (If time permits:) quantum complexity classes, including BQP, QMA, PostBQP, quantum auxiliary advice, hidden subgroup problems, and (local) Hamiltonian problems

Classes During Adverse Weather: Summer (i.e. May – Oct.) is the typhoon/adverse weather season in Hong Kong. It is likely that some classes will be affected. We will follow the University's official policy on adverse weather. For details, please refer to the relevant section in the Undergraduate Student Handbook: General Arrangements for Classes and Examinations on Approach of Typhoons and Rainstorms.

Make-up Quiz/Exam Policy: You may apply for a make-up quiz/exam if all of the following conditions are met:

• You must provide a valid justification along with supporting documentation. For example, in the case of illness, a doctor's note clearly stating your condition is required.
• You must email the instructor at least 4 hours before the start of the lecture in which the quiz is administered.

Genuine emergency cases will be handled separately and typically require valid justification along with supporting documentation.

Policy on Regrading Requests: It is not uncommon for students to disagree with a marker's (such as a TA or the course instructor) grading on exams, quizzes, or homework, and to request additional points. If you plan to do so, please read the following policy carefully to make effective use of both your time and that of the marker.

• Regrading will be considered only if points were lost due to a misunderstanding of your written answer by the marker.

In such cases, you are encouraged to clarify your original response so that the marker can reassess it based on what you actually wrote. However, regrading will not be considered if your justification relies on additional reasoning or explanation that was not included in your original written answer. The principle is simple: grading must be based solely on what was written during the exam or assignment; there is no fair way to take into account explanations provided after the fact, especially since different students may present different arguments about what they meant to write or how they were thinking during the exam.

Please also note that some questions, such as short-answer, calculation, or proof-based questions, do not have simple yes/no answers and often require multiple steps. It is common for students to argue:

• "I know my answer is incorrect, but it's not 'that wrong.' I included some useful steps, or at least showed that I was on the right track, even though I didn't finish or get the correct final answer. So I believe I deserve partial credit, or more partial credit than what I received."

If you are planning to make this kind of argument, please save your effort. The marker will not adjust your score based on such reasoning. If your answer is incomplete or incorrect, the amount of partial credit is determined entirely by the marker and applied consistently across all students. No special consideration will be given to any individual, either in your favor or against you. Allowing such exceptions would introduce unfairness, as it would depend on the student's ability to argue and the emotional state of the marker, which we aim to avoid.

That said, if you believe your answer was completely correct and that you lost points only because the marker misunderstood your writing, then you are welcome to request a re-evaluation.

Academic Honesty: Students are reminded to carefully review and adhere to the University's policies and regulations on academic honesty, as well as the disciplinary guidelines and procedures governing breaches of these rules. We emphasize the importance of strictly following all examination regulations. During an exam, if an invigilator observes behavior deemed suspicious or potentially indicative of academic dishonesty, they are authorized to issue a warning, record the student's name, and report the incident directly to the Faculty Disciplinary Committee (FDC) for investigation. If the FDC determines that a violation has occurred, the student will receive an automatic failure for the course and may face additional disciplinary actions in accordance with University policy.

All students are strongly encouraged to familiarize themselves with the University's official guidelines on examination conduct and academic integrity. Please refer to the following links:

• Honesty in Academic Work: A Guideline for Students and Teachers
• Guidelines from the Engineering Faculty

In particular, the following sections are relevant to course examinations:

• Rules to be Observed by Candidates at Examination Centre
• CUHK disciplinary guidelines and procedures

Students with Special Educational Needs (SEN): CUHK is committed to promoting equal opportunities in academic pursuits for all students. To support full-time students with special educational needs (SEN) in fully participating in campus life and enhancing their learning experience, the SEN Service (SENS) provides tailored support based on individual needs. These may include learning aids and equipment, special arrangements for classes or examinations, accessible facilities, and assistance with hostel visits and accommodations.

Students who require these services should first register with the Office of Student Affairs (OSA) and undergo an assessment by the SEN team. If a student is identified as needing SEN support, the recommended academic accommodations will be communicated to the SEN coordinator of the relevant teaching unit, who will then inform the course instructor accordingly. If you have completed the registration and assessment process with the SEN team at OSA, please email the course instructor to discuss arrangements that best accommodate your needs.

Use of AI tools: This course follows "Approach 2 – Use only with prior permission" according to the University's policy on the use of AI tools. In particular, the use of AI tools is prohibited in all assessment-related components (including quizzes, the midterm, and the final exam). However, students are permitted to use AI tools for non-assessed learning activities, such as practicing exercise problems that do not count toward the final grade.