CS 599: Mathematical Methods for Theoretical CS, Spring 2022

Course Overview

This class will cover a hodgepodge of mathematical tools that one frequently encounters when doing research in algorithm design and theoretical computer science. The learning objectives of the course are to:
Instructor:   Mark Bun, mbun [at] bu [dot] edu
Instr. Office Hours:   Mon 5:00-6:00 (MCS 114)
    Wed 2:00-3:00 (MCS 114)
Class Times:   Tue, Thu 5:00-6:15 (MCS B33)
Exercise Session:   Fri 4:00-6:00 (MCS B21)

Important Links

Course Website: https://cs-people.bu.edu/mbun/courses/599_S22. The website contains the course syllabus, schedule with assigned readings, homework assignments, and other course materials.

Piazza: piazza.com/bu/spring2022/cs599b1. Ask me for the signup code if you don't already have it. 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 RWPEYR. Homework assignments are to be submitted to Gradescope in PDF format.


The formal prerequisite is an A or A- in at least one of CS 530, 531, 535, or 537. In reality, this is a proxy for the following background: Strong undergraduate-level preparation in math (combinatorics, graph theory, discrete probability, calculus, linear algebra, and abstract algebra), algorithms (asymptotic notation, running time analysis, graph algorithms, greedy algorithms, divide-and-conquer, dynamic programming), and theory of computation (Turing machines, decidability, P, NP, reductions). Comfort independently reading and writing mathematical arguments that arise in computer science. Please talk to me if you are missing any of this preparation.

List of potential topics

(Perpetually Tentative) Schedule

Date Topics Reading Handouts/Assignments
Thu 1/20 Course welcome, basics of Boolean Fourier analysis [O'D] 1.1-1.4, Lec1
Tue 1/25 BLR test, influence [O'D] 1.5-1.6, 2.1-2.2, Lec2
Thu 1/27 More on influence, stability [O'D] 2.2-2.5, Lec3 EX1
Tue 2/1 Spectral concentration, low-degree learning [O'D] 3.1-3.2, 3.4, Lec4
Thu 2/3 Majority and the Central Limit Theorem [O'D] 5.1-5.2, Lec5 EX2
Tue 2/8 Intro to hypercontractivity [O'D] 9.1, Lec6
Thu 2/10 Hypercontractivity continued [O'D] 9.2, 9.5, 9.6, Lec7 EX3, HW1, HW1 source
Tue 2/15 Intro to pseudorandomness, bounded independence [Vad] 2.1-2.3, 3.5, Lec8
Thu 2/17 Concentration, PRGs, small-bias distributions [Vad] 3.5, Lec9 EX4
Tue 2/22 No Class - Virtual Monday
Thu 2/24 Bounded independence fools AC0 Braverman, Lec10 EX5
Tue 3/1 Polynomial constructions, intro to extractors [O'D] 4.4, [Vad] 6.1, Lec11
Thu 3/3 More on extractors, Nisan's PRG [Vad] 6.1, 6.2.1, Lec12 HW2, HW2 source
Tue 3/8 No Class - Spring Break
Thu 3/10 No Class - Spring Break
Tue 3/15 No Class - Instructor travel
Thu 3/17 No Class - Instructor travel
Tue 3/22 Intro to spectral graph theory, Laplacian and its eigenvalues [Tre] 3, [Spi] 2-3, Lec13
Thu 3/24 Conductance, Cheeger's inequality [Tre] 4, 5, [Spi] 20-21, Lec14 HW2 due, project topics due (Fri), EX6
Tue 3/29 Random walks [Spi] 10, Lec15
Thu 3/31 Expanders and applications [Vad] 4.1-4.2, Lec16 EX7
Tue 4/5 More on expanders, resistor networks (optional: [Vad] 4.3), [Spi] 11.7-11.9, 12.1-12.4, Lec17
Thu 4/7 Resistor networks, spectral sparsification [Spi] 11.7-11.9, 12.1-12.4, 32, Lec18 EX8
Tue 4/12 Error-correcting codes, linear codes [GRS] 1-2, Lec19 HW3, HW3 source
Thu 4/14 Existential bounds, Reed-Solomon codes [GRS] 4-5, 10, Lec20 EX9, Project proposal due (Fri)
Tue 4/19 Justesen codes, expander codes [GRS] 10-11, Lec21
Thu 4/21 LDPC decoding, linear programming [GRS] 16, LP book, Lec22 EX10
Tue 4/26 Duality, SDPs, Max Cut LP book, Goemans-Williamson, Lec23
Thu 4/28 CSPs, Sherali-Adams Lec24 EX11
Tue 5/3 Pseudoexpectations, Sum-of-Squares Lec25
Wed 5/11, Fri 5/13 Project report and peer feedback due

Texts and References

You do not need to buy a textbook for this class. Required reading will come from sources that are either freely available on the web or accessible using your BU institutional login. The abbreviated references in the schedule are to the following textbooks and monographs.

[O'D] Ryan O'Donnell, Analysis of Boolean Functions. [arXiv] [publisher]
[GRS] Venkatesan Guruswami, Atri Rudra, and Madhu Sudan, Essential Coding Theory. [public full]
[Juk] Stasys Jukna, Extremal Combinatorics: With Applications in Computer Science. [publisher] (You can download a PDF using your BU ID)
[Spi] Daniel Spielman, Spectral and Algebraic Graph Theory. [draft in preparation]
[Tre] Luca Trevisan, Notes on Graph Partitioning, Expanders, and Spectral Methods. [notes]
[Vad] Salil Vadhan, Pseudorandomness. [public full] [publisher]

It may also be helpful to review the notes from similar courses offered at other institutions that inspired this one.
Arora [2007]
Praladh and Srivastava [2021]
Kelner [2009]
Khan and Louis [2020]
Li [2021]
O'Donnell [2020]
Vempala [2016]


Your grade in the course will be determined by exercises, homework assignments, a research project, and class participation.

Exercises (15%)

At the beginning of the semester, we will find a mutually convenient time to hold an exercise session. We will break into small groups to work together on short exercises aimed at digesting the week's material. Solutions to exercises should be turned in via Gradescope either at the end of the session or within 24 hours. Attending the sessions themselves is not mandatory, but will hopefully working together will provide a more rewarding experience. Exercises will be evaluated based on whether you made a good faith effort to answer most of the questions, and your two lowest exercise set scores will be dropped to accommodate extenuating circumstances.

Homework (45%)

There will be four or five problem sets distributed during the semester. Homework sets are designed to be challenging, so you will want to start early to give yourself time to think deeply about the problems. Even so, do not be discouraged if you cannot completely solve all of the problems, and we welcome well-reasoned partial ideas toward solutions. Since I try to distribute homework solutions immediately after the deadlines, I cannot accept late homework without an advance prior arrangement.

You are allowed, and indeed encouraged, to collaborate with up to 3 other students on solving the homework problems. However, you must write the solutions independently in your own words and acknowledge your collaborators.

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.)

For your convenience, I 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.

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.

Course Project (30%)

The course will culminate in a final project. It can take one of several forms including, but not limited to 1) a formulation of and progress toward a research problem related to one of the course topics, 2) a survey synthesizing several related research results concerning one of the course topics, or 3) a self-contained exposition of a mathematical tool not discussed in class and its application to a problem in theoretical computer science. Your written report should be targeted to other students in the class, and part of the project includes supplying constructive feedback to your fellow students. You are strongly encouraged to work in pairs on the project. Depending on enrollment, we will hopefully be able to devote the last few class periods to project presentations. Details are forthcoming.

Project Guidelines

Class Participation (10%)

Your active participation during class meetings will make it much more enjoyable for you (and for me!). You can also earn participation credit by asking thoughtful questions on Piazza or during office hours. Midway through the semester, I will send you indication of how your participation in class is going.

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.