| Instructor: | Mark Bun, mbun [at] bu [dot] edu | |
| Instr. Office Hours: | Thu 5PM-6PM (CDS 1021) | |
| Teaching Fellow: | Mandar Juvekar, mandarj [at] bu [dot] edu | |
| TF Office Hours: | Fri 10:30-11:30AM (CDS 10th Floor Yellow Lounge) | |
| Class Times: | Tue, Thu 2:00PM-3:15PM (MCS B31) | |
| Discussion Sections: | Wed 1:25PM-2:15PM (CDS 801) | |
| Wed 2:30PM-3:20PM (CDS 801) |
Course Website: https://cs-people.bu.edu/mbun/courses/535_F26. The website contains the course syllabus, schedule with assigned readings, homework assignments, and other course materials.
Piazza: https://piazza.com/bu/fall2026/cs535. The entry code will be emailed to all registered students just prior to the start of the semester; please let the course staff know if you need it sent to you directly. All class announcements will be made through Piazza, so please set your notifications appropriately. Please post questions about the course material to Piazza instead of emailing the course staff directly. It is likely that other students will have the same questions as you and may be able to provide answers in a more timely fashion. Active participation on Piazza may add extra points to your participation grade.
Gradescope: https://gradescope.com. Sign up for a student account on Gradescope using your BU email address. The entry code for the course is PRXGDP. Homework assignments are to be submitted to Gradescope in PDF format.
Covers topics of current interest in the theory of computation chosen from computational models, games and hierarchies of problems, abstract complexity theory, informational complexity theory, time-space trade-offs, probabilistic computation, and recent work on particular combinatorial problems.
CS 330 (Introduction to Analysis of Algorithms) is required. CS 332 (Theory of Computation) or a similar rigorous undergraduate introduction to the theory of computation is recommended. Aside from the formal prerequisite, it's important to have "mathematical maturity": Comfort with mathematical abstraction, a solid understanding of basic combinatorics and discrete probability, and the ability to read, understand, and write mathematical proofs.
Readings listed for a class are intended to be previewed before that class.
| Date | Topics | Arora-Barak Reading | Handouts/Assignments |
|---|---|---|---|
| Thu 9/3 | Course welcome, Turing machines, decidability | 0, 1.1-1.5, 1.7 (optional), A.1-A.2, Lec01 | HW 1 out |
| Tue 9/8 | Undecidability, time complexity, P, NP | 1.4-1.6, 2.1, 2.6-2.7, Lec02 | |
| Thu 9/10 | More on NP, NP-completeness | 2.2-2.4, Lec03 | HW 1 due Fri 9/11; HW 2 out |
| Tue 9/15 | Cook-Levin Theorem, decision vs. search | 2.3, 2.5 | |
| Thu 9/17 | Hierarchy theorems, Ladner's Theorem | 3.1-3.3, 4.1.3 | Quiz 1; HW 2 due Fri 9/18; HW 3 out |
| Tue 9/22 | Relativization, Space complexity | 3.4, 4.1 | |
| Thu 9/24 | Savitch's Theorem, PSPACE, PSPACE-completeness | 4.2 | Quiz 2; HW 3 due Fri 9/25; HW 4 out |
| Tue 9/29 | Logspace computation | 4.3 | |
| Thu 10/1 | Immerman-Szelepcsényi Theorem, Polynomial hierarchy | 4.3, 5.1-5.2 | Quiz 3; HW 4 due Fri 10/2; HW 5 out |
| Tue 10/6 | PH via oracles, alternation | 5.3, 5.5 | |
| Thu 10/8 | More alternation, time-space tradeoffs | 5.3-5.4 | Quiz 4; HW 5 due Fri 10/9; HW 6 out |
| Tue 10/13 | NO CLASS (Substitute Monday schedule) | ||
| Thu 10/15 | Circuits, non-uniform computation | 6.1-6.3 | Quiz 5; HW 6 due Fri 10/16; HW 7 out |
| Tue 10/20 | Karp-Lipton Theorem, circuit lower bounds, restricted circuit classes | 6.4-6.7 | |
| Thu 10/22 | Probabilistic algorithms | A.2, 7.1-7.2 | Quiz 6; HW 7 due Fri 10/23; HW 8 out |
| Tue 10/27 | Randomized time classes, concentration inequalities | A.2, 7.3-7.4 | |
| Thu 10/29 | Error reduction, BPP vs. P/poly, BPP vs. PH | 7.4-7.5 | Quiz 7; HW 8 due Fri 10/30; HW 9 out; research project topic due Fri 10/30 |
| Tue 11/3 | PromiseBPP, randomized reductions, Valiant-Vazirani Theorem | 7.5, 17.4.1 | |
| Thu 11/5 | Counting, #P | 17.1-17.3.1 | Quiz 8; HW 9 due Fri 11/6; HW 10 out |
| Tue 11/10 | #P-completeness | 17.2-17.3 | |
| Thu 11/12 | Toda's Theorem, Interactive proofs | 17.4, 8.1 | Quiz 9; HW 10 due Fri 11/13 |
| Tue 11/17 | Arthur-Merlin classes | 8.2 | |
| Thu 11/19 | IP = PSPACE | 8.3 | Quiz 10; HW 11 out |
| Tue 11/24 | PCP Theorem, hardness of approximation | 11.1-11.3 | |
| Thu 11/26 | NO CLASS — Happy Thanksgiving! | ||
| Tue 12/1 | More hardness of approximation, proof of PCP Mini | 11.4-11.5 | |
| Thu 12/3 | Special topic TBD | TBD | HW 11 due Fri 12/4 |
| Tue 12/8 | Special topic TBD | TBD | Research presentations in tutorials/discussion |
| Thu 12/10 | Special topic TBD | TBD | |
| Tue 12/15 | Final Exam 3-5PM (MCS B31) |
Oded Goldreich, Computational Complexity: A Conceptual Perspective.
Steven Homer and Alan L. Selman, Computability and Complexity Theory.
Cristopher Moore and Stephan Mertens, The Nature of Computation.
Christos H. Papadimitrou, Computational Complexity.
Michael Sipser, Introduction to the Theory of Computation.
Avi Wigderson, Mathematics and Computation.
We acknowledge that this class has a large number of different deliverables. The purpose of these is absolutely not to overwhelm or overburden you, or make you feel like you have to complete every single requirement to succeed in the course. (We understand that you are busy graduate students and that making progress on your research comes first!) Our intent, rather, is to offer you many opportunities to earn credit for the various positive learning activities (reading, writing, problem solving, speaking) that you are likely doing anyway to engage seriously with the material, and to reward you for practicing the skills that will help you throughout your research careers. Note also that most course components have built-in flexibility; homework assignments contain more practice problems than you are required to submit, your lowest quiz score is dropped, you only need to submit ten reading responses during the semester, and missing a small number of discussion or tutorial sessions will not adversely affect your participation score.
Unless otherwise specified, you may use generative AI systems on work that you complete outside of class, including homework, pre-reading and reading responses, and the written portion of the research reading project. Our goal is not to police which tools you use outside the classroom, but to structure the course so you are incentivized to use such tools to facilitate your learning rather than replace it. Take-home activities are primarily opportunities to practice, receive feedback, and prepare; in-class quizzes and the final exam are where you will be asked to demonstrate your own understanding without outside assistance. In our experience, generative AI can be useful in clarifying notation, finding definitions, generating examples, or critiquing an attempted argument. But simply reviewing an AI-generated solution offers a much shallower learning experience than producing one oneself.
There will be weekly homework assignments due each Friday at 11:59PM. Homework sets are designed to be challenging, so you will want to start early to give yourself time to think deeply about the problems. Each assignment will typically contain more material than you are expected to submit. Some problems may be designated as "required" problems. You must submit solutions to "required" problems and may be asked to choose among the remaining problems. Problems that you do not submit solutions to are useful for additional practice.
Homework will be graded primarily for completion rather than correctness. A serious attempt at a problem can receive full homework credit even if the argument is ultimately incorrect. In addition to the official homework grade that counts toward your course grade, we will provide detailed written feedback and a separate "diagnostic score" indicating how well the submitted solutions would have done if, say, it had appeared on an exam. This diagnostic score does not affect your course grade.
You are allowed, and indeed encouraged, to collaborate with other students on solving the homework problems. You may also use books, online resources, generative AI systems, or other tools. However, note that the main purpose of homework is to give you practice solving difficult problems, reveal gaps in your understanding, and give us an opportunity to provide feedback on your reasoning. Submitting a correct solution that you do not understand may earn homework credit, but is unlikely to prepare you well for in-class tests.
You are also encouraged to flag parts of your solutions about which you are uncertain, identify questions that arose while working on a problem, or otherwise indicate where you would particularly like feedback. We might even ask you such "meta" questions as part of an assignment.
Homework solutions must be typeset. LaTeX is the standard document preparation system used in the mathematical sciences, but you are also free to use other tools such as Microsoft Word. If you wish to include drawings or figures, you may draw them by hand and incorporate the images into your documents. (There are packages for creating images within LaTeX, but they can be unnecessarily time-consuming to use.)
My preferred LaTeX editors are TexShop for Mac and TexStudio for Windows. If you would like to give LaTeX a try on the web without installing anything on your computer, Overleaf is a good option.
Not so short intro to LaTeX. A LaTeX tutorial.
For your convenience, we will supply the LaTeX source for each assignment along with the compiled PDF. Changing the flag \inclsolns from 0 to 1 will let you add your name and solutions directly to the assignment. The file should be in the same directory for it to compile correctly.
There will be roughly ten short in-class quizzes, normally on Thursdays. The quiz sequence will begin after the first two weeks of class and will end before Thanksgiving. Your lowest quiz score will be dropped.
Quizzes are to be completed individually and without outside resources. Each quiz will take approximately 15 minutes and will typically contain one short conceptual question and one short proof or problem-solving question. The quizzes are not intended to be speed tests; we will aim to write them so that a well-prepared student can finish comfortably in the allotted time. Quiz questions will frequently build on ideas from the most recently discussed homework assignment, but will generally ask you to apply those ideas in a new setting rather than reproduce a homework solution verbatim. Quiz questions may also revisit material from earlier in the semester.
A comprehensive in-class final will be held on Tuesday, December 15 from 3-5PM in MCS B31. There will be no midterm exam.
You may bring two double-sided 8.5" x 11" sheets of notes to the final. Note sheets may be either handwritten or typeset. You may not use any other aids during the exam, including but not limited to books, lecture notes, calculators, phones, or laptops.
At the end of the course, you will complete a mini-project that involves independently reading and synthesizing a research article, survey, or small collection of related papers in complexity theory. The goal is to gain experience identifying the main questions and results in a piece of research, understanding important proof ideas, and connecting the work to material from the course.
The project will include a short written report and a brief presentation/discussion of your reading with the course staff and other students. These presentations and discussions will take place during tutorial and/or discussion sections near the end of the semester rather than during lecture. Details for the assignment will be provided shortly.
Reading Responses: Almost every lecture will have an associated reading that is intended to be previewed before class. The goal of this pre-reading is not to master every proof on your own. Instead, try to identify the main definitions and results, get a rough sense of the arguments, and notice what you do not yet understand. We will usually indicate which portions deserve close attention and which technical details are safe to skim. You should ordinarily spend about 20-30 minutes making a serious first pass through the reading.
To help keep you in the habit of actively engaging with technical reading, you are asked to submit ten (10) brief reading responses to Piazza over the course of the semester. You may choose which readings to respond to, but each response must be submitted before noon on the lecture corresponding to that reading. You should expect to submit a response in most weeks, but the requirement is deliberately somewhat less than once per week on average.
A reading response consists of at least one insightful question or comment about something specific in the assigned reading. A response does not need to demonstrate complete understanding: identifying the precise point where a definition or proof becomes confusing can be an excellent response. Generic summaries of the assigned material generally do not count as substantive responses. Submitted responses are helpful to us in deciding which of the material to emphasize in lecture.
Here are some suggestions to guide your thinking as you comment on the reading.
If you are not comfortable attaching your name to your comment, you may post as "anonymous to classmates."
(These guidelines are adapted from Salil Vadhan's CS221 and other courses.)
Discussion Sections and Tutorials:Every student will participate in a small-group "tutorial" each week. Tutorials will normally take place on Monday or Tuesday and will focus on getting started on the homework assignment currently in progress. The purpose is not to present solutions, but to practice the process of beginning a difficult problem: trying examples, unpacking definitions, proposing approaches, discovering why an approach fails, and deciding what to try next. Tutorial time counts as part of the expected time spent working on homework.
Wednesday discussion sections will typically spend some time revisiting one problem from the previous homework assignment, with the choice informed by student questions and common issues we see while grading. We will also work through an additional review or new problem. We may ask students to present or discuss their approaches, but solutions to discussion problems will not themselves be graded.
We will record active attendance in weekly discussion sections and tutorials. A small number of absences will not affect your participation grade. Your participation score can also be supplemented by thoughtfully asking and answering questions in lectures, in discussions, on Piazza, or during office hours.