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