CS 535: Complexity Theory, Fall 2020
The goal of computational complexity theory is to understand the capabilities and fundamental limitations of efficient computation
. In this course, we will ask questions such as, "What kinds of computational problems are inherently difficult?" in that solving them requires massive running times, no matter how cleverly one tries to design algorithms. In addition to running time, we will also quantify efficiency in terms of the use of other computational resources including space (memory), randomness, nondeterminism, interaction, communication, and algebraic operations.
The learning objectives of the course are to:
- Learn the types of problems studied in computational complexity theory: decision, search, counting, optimization, proof verification.
- Learn how to use complexity classes to categorize these problems according to the computational resources needed to solve them.
- Learn the "tools of the trade": How techniques such as diagonalization, reductions, completeness, simulation, and a host of probabilistic and combinatorial techniques can be used to relate seemingly unrelated problems and complexity classes.
- Learn how fundamental philosophical questions about the nature of efficient computation (Can every problem for which we can quickly verify a solution also be solved efficiently? Is an interactive conversation more powerful than a one-shot proof? Why is actually answering these quesitons so difficult?) can be formalized as precise mathematical problems.
- Gain experience with creative mathematical problem solving and develop the ability to write correct, clear, and concise mathematical proofs.
||Mark Bun, mbun [at] bu [dot] edu
|Instr. Office Hours:
||Tue 10-11, Thu 5-6
||Ludmila Glinskih, luda [at] bu [dot] edu
|TF Office Hours:
||Wed 9-10, Fri 10-11
||Tue, Thu 3:30-4:45 (Online)
||Wed 3:35-4:25 (Online and MCS B37)
||Wed 4:30-5:25 (Online and MCS B37)
Course Website: https://cs-people.bu.edu/mbun/courses/535_F20. The website contains the course syllabus, schedule with assigned readings, homework assignments, and other course materials.
Piazza: https://piazza.com/bu/fall2020/cs535. 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 MW8845. 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.
List of potential topics
- Fundamental Turing machine classes. Time complexity: P, NP, EXP and related classes. Reductions and completeness. Hierarchy theorems. Space complexity: L, NL, PSPACE. Randomized computation: BPP, RP. Alternation and the polynomial hierarchy. Time-space tradeoffs. Relativization and why diagonalization isn't enough to resolve P vs. NP.
- Complexity of proving and verifying. Interactive proofs: MA, AM, IP. Proof of IP = PSPACE. Proabilistically checkable proofs and hardness of approximation.
- Circuits and concrete computational models. Basic circuit complexity: P/poly, NC, AC. Karp-Lipton Theorem. Circuit lower bounds. Switching Lemma. Decision trees. Communication complexity.
- Complexity of counting. Counting classes: #P, PP. Toda's Theorem. Approximate counting.
- Advanced topics. Pseudorandomness and derandomization. Average-case complexity. Algebraic complexity. Quantum computation. Unique Games Conjecture. Proof complexity. Frontier circuit lower bounds.
(Perpetually Tentative) Schedule
||Course welcome, Turing machines, decidability
||0, 1.1-1.5, 1.7 (optional), A.1-A.2
||Collaboration Policy, Survey, hw1.pdf, hw1.tex, macros.tex
||Time complexity, P, NP, NP-completeness
||1.6, 2.1-2.2, 2.6-2.7
||More on NP-completeness, Cook-Levin Theorem
||HW 1 due (Fri), hw2.pdf, hw2.tex
||Decision vs. search, hierarchy theorems
||2.5, 3.1-3.2, 4.1.3
||Ladner's Theorem, relativization barrier
||HW 2 due (Fri), hw3.pdf, hw3.tex
||Space complexity, Savitch's Theorem
||HW 3 due (Fri), test 1 out
||Logspace computation, Immerman-Szelepcsényi Theorem
||Take-home test 1 due (Fri), hw4.pdf, hw4.tex
||PH via oracles, alternation
||Alternation, time-space tradeoffs
||HW 4 due (Fri), hw5.pdf, hw5.tex
||NO CLASS (Virtual Monday)
||Circuits, non-uniform computation
||HW 5 due (Fri), hw6.pdf, hw6.tex
||Circuit lower bounds
||HW 6 due (Fri), test 2 out
||Randomized time classes, error reduction
||BPP vs. P/poly, BPP vs. PH
||Take-home test 2 due (Fri), hw7.pdf, hw7.tex
||PromiseBPP, randomized reductions, Valiant-Vazirani Theorem
||Counting, #P, #P-completeness
||HW 7, paper topic due (Fri), hw8.pdf, hw8.tex
||Toda's Theorem, approximate counting and sampling
||HW 8 due (Fri)
||SAT solving and fine-grained complexity (Luda)
||Term paper draft due (Fri)
||IP = PSPACE
||Draft feedback due (Wed)
||NO CLASS — Happy Thanksgiving!
||PCP Theorem, hardness of approximation
||More hardness of approximation, proof of PCP Mini
||HW 9 due (Fri)
||Circuit lower bounds (Parity is not in AC0)
||test 3 out
||NEXP is not in ACC0
||Web Appendix B
||Term paper due
||FINAL EXAM SLOT
||Take-home test 3 due (5PM), final feedback due (Fri)
Texts and References
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. ISBN-13: 978-0521424264.
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.
Your grade in the course will be determined by homework assignments, three take-home tests, a term paper, and class participation.
There will be weekly homework assignments due each Friday at 8PM. 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 assigments may 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. Collaboration is NOT allowed on bonus problems.
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.
Take-Home Tests (25%)
There will be three take-home tests, two during the semester and one due at the end of our regularly scheduled final exam period. Each test will be about as long as a homework assignment and you will have a week to complete it. Unlike homework assignments, these are to be completed individually and without the use of external resources.
Term Paper (25%)
The course will culminate in a final project which will involve 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.
Term Paper Instructions
Class Participation (10%)
You are expected to engage thoughtfully with the readings before each class session. This will help us use our time in class together to work through the most important and difficult parts of the material. Reading assignments will be posted on the course website within a few hours of the end of the previous class session. I may also record a short video introducing the reading and suggesting points to pay particular attention to.
We will use Piazza to manage our online discussion of the reading material. Starting with the 9/8 lecture, you are expected to post at least one insightful question or comment about the readings by 9AM on the day of class. (More are encouraged!) Here are some suggestions to guide your thinking as you comment on the reading.
- What points did you find particularly confusing?
- Why do you think particular choices are made in the definitions? What would change if things were defined differently?
- How would you translate an informal statement in the text into a precise mathematical statement? What is the conceptual message underlying a formal mathematical definition or statement?
- How might you simplify the proofs? Or generalize them to prove stronger statements?
- What possible new connections do you see with something else inside or outside the course?
- What new questions do the results raise? (Beyond those explicitly stated as open questions in the text.)
If you are not comfortable posting some questions or comments publicly, you may set their visibility to "instructors only."
Your participation grade can be supplemented by thoughtfully asking and answering questions in lectures, in discussions, on Piazza, or during office hours. However, students who are not able to participate in the class synchronously will still be able to earn full participation credit by commenting on the reading on Piazza.
(These guidelines are adapted from Salil Vadhan's CS221 and other courses.)
Course Recording Policy
All class sessions will be recorded for the benefit of registered students who are unable to attend live sessions (either in person or remotely) due to time zone differences, illness or other special circumstances. Recorded sessions will be made available to registered students ONLY via a password-protected BU MyMedia channel. Students may not share these recordings with anyone not registered in the course and may not repost them in a public platform.
Students have the right to opt-out of being part of the class recording. Please contact your instructor or teaching assistant to discuss options for participating in the course while opting out of the class recording.
No student may record any classroom or other academic activity (including advising sessions or office hours) without my express written consent. Unauthorized use of classroom recordings – including distributing or posting them – is also prohibited. If you have (or think you may have) a disability such that you need to record classroom activities, or need other assistive services, you should contact Disability & Access Services (see below) to request an appropriate accommodation.
All Boston University students are expected to maintain high standards of academic honesty and integrity. It is your responsibility to be familiar with the Academic Conduct Code, which describes the ethical standards to which BU students are expected to adhere and students’ rights and responsibilities as members of BU’s learning community. All instances of cheating, plagiarism, and other forms of academic misconduct will be addressed in accordance with this policy. Penalties for academic misconduct can range from failing an assignment or course to suspension or expulsion from the university.
Students are expected to attend each class session unless they have a valid reason for being absent. If you must miss class due to illness or another reason, please notify the instructor as soon as possible, ideally before the absence.
Absence Due to Religious Observance
If you must miss class due to religious observance, you will not be penalized for that absence and you will receive a reasonable opportunity to make up any work or examinations that you may miss. Please notify the instructor of absences for religious observance as soon as possible, ideally before the absence.
In the event of the death of an immediate family member, you should notify your advisor, who will help you coordinate your leave. You will be automatically granted five weekdays of leave, and if necessary, you advisor will help you to petition the Dean for additional leave time. You may also request a leave of absence due to bereavement. Please contact your advisor, who will help you with the process.
Students with documented disabilities, including learning disabilities, may be entitled to accommodations intended to ensure that they have integrated and equal access to the academic, social, cultural, and recreational programs the university offers. Accommodations may include, but are not limited to, additional time on tests, staggered homework assignments, note-taking assistance. If you believe you should receive accommodations, please contact the Office of Disability Services to discuss your situation. This office can give you a letter that you can share with instructors of your classes outlining the accommodations you should receive. The letter will not contain any information about the reason for the accommodations.
If you already have a letter of accommodation, you are encouraged to share it with your instructor as soon as possible.
Disability & Access Services
25 Buick Street, Suite 300
If you feel that you have received an arbitrary grade in a course, you should attempt to meet with the grader before filing a formal appeal. If the student and the instructor are unable to arrive at a mutually agreeable solution, the student may file a formal appeal with the chair. This process must begin within six weeks of the grade posting. To understand how an “arbitrary grade” is defined, please explore the following link.
An incomplete grade (I) is used only when the student has conferred with the instructor prior to the submission of grades and offered acceptable reasons for the incomplete work. If you wish to take an incomplete in this class, please contact the instructor as soon as possible but certainly before the submission of final grades. To receive an incomplete, you and your instructor must both sign an “Incomplete Grade Report” specifying the terms under which you will complete the class.
Student Health Services
Offers an array of health services to students, including wellness education and mental health services (behavioral medicine).
Medical Leave of Absence
If you must take a leave of absence for medical reasons and are seeking to re-enroll, documentation must be provided to Student Health Services so that you may re-enroll. To take a medical leave, please talk with SHS and your advisor, so that they may assist you in taking the best course of action for a successful return.
The International Students & Scholars Office is committed to helping international students integrate into the Boston University community, as well as answering and questions and facilitating any inquiries about documentation and visas.