CS 535: Complexity Theory, Fall 2020

This page is a work in progress and is intended to provide basic information during registration. Everything is subject to change.

Course Overview

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:
Instructor:   Mark Bun, mbun [at] bu [dot] edu
Instr. Office Hours:   TBD (MCS 114)
Teaching Fellow:   TBD
TF Office Hours:   TBD
Class Times:   Tue, Thu 3:30-4:45 (MCS B29)
Discussion Sections:   Wed 3:35-4:25 (MCS B37)
  Wed 4:30-5:25 (MCS B37)

Important Links

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.

Catalog Description

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

(Perpetually Tentative) Schedule

Date Topics Reading/Reference Handouts/Assignments

Texts and References

Required Textbook

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. ISBN-13: 978-0521424264.

Reading the textbook before class and reviewing it after class are important for solidifying your understanding of the course material. Personally, I find the physical textbook to be extremely useful and refer to my copies all the time. However, if the price of the textbook presents a barrier to your learning, you can find a draft version by the authors online here: Arora-Barak draft.. Just beware that section and problem numbers may be different and several sections had yet to be written.

Other Resources

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.


Your grade in the course will be determined by homework assignments, three in-class exams, and class participation.
The following letter grades are guaranteed if you earn the corresponding percentages: A ≥93%, A- ≥90%, B+ ≥87%, B ≥83%, B- ≥80%, C+ ≥75%, C ≥70%. However, to correct for the possibility of assignments and exams being more difficult than anticipated, letter grades may be (significantly) increased above these guarantees based on the overall performance of the class.

Homework (50%)

There will be weekly homework assignments. 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 grades will be dropped.

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.

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.

Homework template files: tex, cls, jpg, pdf.

Midterm (15%) and Final Exam (25%)

There will be a 70-minute in-class midterm exam scheduled for TBD. A comprehensive final exam will be held during the normal 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 exam and two such sheets to the final exam. 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.

Class Participation (10%)

Your active participation in class and in discussion sections is an essential part of your learning. Your participation grade will be determined by thoughtfully asking and answering questions in lectures, in discussions, on Piazza, or during office hours.

Course Policies

Academic Conduct

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.


Attendance Policy

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.


Disability Services

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

Grade Grievances

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.


Incomplete Grades

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.