| Instructor: | Mark Bun, mbun [at] bu [dot] edu | |
| Instr. Office Hours: | Mon 3-4:30 (CDS 1021) | |
| Thu 5-6 (CDS 1021) | ||
| Teaching Fellow: | Mandar Juvekar, mandarj [at] bu [dot] edu | |
| TF Office Hours: | Tue 3:30-4:30 (CDS 1001) | |
| Fri 10:30-11:30 (CDS 614) | ||
| Class Times: | Tue, Thu 2:00-3:15 (MCS B31) | |
| Discussion Section: | Wed 11:15-12:05 (BRB 121) |
Course Website: https://cs-people.bu.edu/mbun/courses/535_F23. The website contains the course syllabus, schedule with assigned readings, homework assignments, and other course materials.
Piazza: https://piazza.com/bu/fall2023/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 ZWZGPW. 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 332 (Theory of Computation) or a similar rigorous undergraduate introduction to the theory of computation. 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. If you have not completed the prerequisites for the course, please schedule a meeting with me before registering.
| Date | Topics | Arora-Barak Reading | Handouts/Assignments |
|---|---|---|---|
| Tue 9/5 | Course welcome, Turing machines, decidability | 0, 1.1-1.5, 1.7 (optional), A.1-A.2 L1 notes | Collaboration Policy, Survey, hw1.pdf, hw1.tex, macros.tex |
| Thu 9/7 | Time complexity, P, NP, NP-completeness | 1.6, 2.1, 2.6-2.7 L2 notes | |
| Tue 9/12 | NP-completeness, Cook-Levin Theorem | 2.2-2.4 L3 notes | HW 1 due, hw2.pdf, hw2.tex |
| Thu 9/14 | Decision vs. search | 2.5 L4 notes | |
| Tue 9/19 | Hierarchy theorems, Ladner's Theorem | 3.1-3.3, 4.1.3 L5 notes | HW 2 due, hw3.pdf, hw3.tex |
| Thu 9/21 | Relativization, Space complexity | 3.4, 4.1 L6 notes | |
| Tue 9/26 | Savitch's Theorem, PSPACE, PSPACE-completeness | 4.2 L7 notes | HW 3 due, hw4.pdf, hw4.tex |
| Thu 9/28 | Logspace computation | 4.3 L8 notes | |
| Tue 10/3 | Immerman-Szelepcsényi Theorem, Polynomial hierarchy | 4.3, 5.1-5.2 L9 notes | HW 4 due, hw5.pdf, hw5.tex |
| Thu 10/5 | PH via oracles, alternation | 5.3, 5.5, L10 notes | |
| Tue 10/10 | NO CLASS (Virtual Monday) | ||
| Thu 10/12 | More alternation, time-space tradeoffs | 5.3-5.4, L11 notes | |
| Tue 10/17 | Circuits, non-uniform computation | 6.1-6.3, L12 notes | HW 5 due, hw6.pdf, hw6.tex |
| Thu 10/19 | Karp-Lipton Theorem, circuit lower bounds, restricted circuit classes | 6.4-6.7, L13 notes | |
| Tue 10/24 | Midterm Exam | ||
| Thu 10/26 | Probabilistic algorithms | A.2, 7.1-7.2, L14 notes | |
| Tue 10/31 | Randomized time classes, concentration inequalities | A.2, 7.3-7.4, L15 notes | HW 6 due, term paper topic due, hw7.pdf, hw7.tex |
| Thu 11/2 | Error reduction, BPP vs. P/poly, BPP vs. PH | 7.4-7.5, L16 notes | |
| Tue 11/7 | PromiseBPP, randomized reductions, Valiant-Vazirani Theorem | 7.5, 17.4.1, L17 notes | HW 7 due, hw8.pdf, hw8.tex |
| Thu 11/9 | Counting, #P | 17.1-17.3.1, L18 notes | |
| Tue 11/14 | #P-completeness | 17.2-17.3, L19 notes | HW 8 due, hw9.pdf, hw9.tex |
| Thu 11/16 | Toda's Theorem, Interactive proofs | 17.4, 8.1, L20 notes | |
| Tue 11/21 | Arthur-Merlin classes | 8.2, L21 notes | Term paper draft due |
| Thu 11/23 | NO CLASS — Happy Thanksgiving! | ||
| Tue 11/28 | IP = PSPACE | 8.3, L22 notes | |
| Thu 11/30 | PCP Theorem, hardness of approximation | 11.1-11.3, L23 notes | Term paper feedback due |
| Tue 12/5 | More hardness of approximation, proof of PCP Mini | 11.4-11.5, L24 notes | HW 9 due |
| Thu 12/7 | Quantum circuits | 10.1-10.3, L25 notes | |
| Tue 12/12 | Grover's algorithm | 10.4, L26 notes | Term paper due |
| Tue 12/19 | Final Exam 3-5PM |
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.
There will be weekly homework assignments due each Tuesday 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. No late homework will be accepted. To accomodate extenuating circumstances, your lowest homework grade will be dropped. Further accomodations require a note from your academic advisor.
You are allowed, and indeed encouraged, to collaborate with other students on solving the homework problems. However, you must write the solutions independently in your own words. Details of the collaboration policy may be found here: Collaboration and Honesty Policy
Some homework assignments will include clearly marked "individual review" problems. These problems are meant to reinforce concepts from previous assignments that you've already received feedback on. These problems are to be completed individually; no collaboration is allowed.
Some homework assigments may also include optional "bonus" problems. Solving these problems will not directly contribute to your homework grade but may improve the letter grade you receive in the course if the final percentage we calculate is on the borderline between two letter grades. Solving bonus problems is also a good way to impress your instructor if you are seeking a recommendation letter, research opportunities, or a grading position.
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, collaborators, and solutions directly to the assignment. The file macros.tex should be in the same directory for it to compile correctly.
There will an in-class midterm on Tuesday, October 24. A comprehensive in-class final will be held during our registrar-appointed two-hour exam slot. Please wait until the official University final exam schedule is finalized before making your end-of-semester travel plans.
You may bring one double-sided 8.5" x 11" sheet of notes to the midterm test and two such sheets 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 final mini-project that involves writing a 5-10 page review of a research article or survey in complexity theory. Your review should be targeted to other students in the class. The project will also involve supplying constructive feedback to your fellow students. Term papers may be written individually or in pairs. Details for the assignment are below.
Reading Responses: To help keep you on track with reading assignments, we ask you to submit brief reading responses to Piazza every week. A reading response consists of at least one insightful question or comment about the week's assigned readings. (More are encouraged!) Reading responses are due by 10PM every Sunday, but submissions received before the relevant class period will help us use our time in class together to work through the most important and difficult parts of the material.
Here are some suggestions to guide your thinking as you comment on the reading.
If you are not comfortable posting some questions or comments publicly, you may set their visibility to "instructors only."
(These guidelines are adapted from Salil Vadhan's CS221 and other courses.)
Discussion Sections: We will record active attendance in our weekly discussion sections, but will not grade your solutions to discussion problems.
You can earn full participation credit by completing nine (9) reading responses and attending nine (9) discussion sections. Your participation score can be also supplemented by thoughtfully asking and answering questions in lectures, in discussions, on Piazza, or during office hours.