MIT OpenCourseWare
Topics in Combinatorics: Analysis of Boolean Functions
Art: Johannes Kepler, Konjukce Saturnu a Jupiteru Originál, 1596 · Public domain
- Instructor
- Prof. Dor Minzer
- Term
- Spring 2021
- Level
- Graduate
- What's inside
- 5 problem sets · 1 lecture note · 13 other files · 3 web pages
- Materials open
- MIT OCW
About this course
Source: MIT OpenCourseWare 18.218 Topics in Combinatorics: Analysis of Boolean Functions, Spring 2021, Prof. Dor Minzer — original course page on ocw.mit.edu ↗. License: CC BY-NC-SA 4.0. Study order: none is claimed; materials are grouped by MIT's own sections. Taken from MIT's published course files, downloaded from ocw.mit.edu on September 23, 2026. How RedLectern is built.
Materials are grouped the way MIT organized them. A verified, course-wide order has not been established here.
Before you start
Prerequisites are not listed here. Check MIT's own syllabus for this course.
How this course was organized
What's here, and what isn't
- No lecture or session order could be confirmed for this course.
Not included here
35 items from the source could not be safely included:
- MIT's page format for this item wasn't recognized clearly enough to place it safely. (35 items)
Materials by section
Grouped by section, as MIT organized them. Not sequenced or ordered.
Lecture Notes
13 files
- Lecture 1: Course Overview and the Basic Set-up Download
- Lecture 2: The BLR Lineairty Test and Random Restrictions Download
- Lecture 3: PAC Learning and Learning Sparse Functions Download
- Lecture 4: Influences of Boolean Functions Download
- Lecture 5: Hypercontractive Inequality Download
- Lecture 6: The FKN Theorem and the KKL Theorem Download
- Lecture 7: Talagrand’s Version of the KKL Theorem, the Friedgut Junta Theorem, and Isoperimetric Inequalities Download
- Lecture 15: Introduction to Complexity Theory, Approximation Problems, and the PCP Theorem Download
- Lecture 16: The Goemans-Williamson Algorithm and A Hardness Result for Max-Cut Download
- Lecture 17: Preliminaries, the Reduction, and Analysis of the Reduction Download
- Lectures 8–10: Noise Stability and Arrow’s Impossibility Theorem Download
- Lectures 11–12: Erdos-Ko-Rado Type Theorem, the p-biased Cube, and Properties of Quasi-random Families Download
- Lectures 13–14: Invariance Principle, the Berry-Essen Theorem, and Hypercontractivity in Gaussian Space Download
Assignments
MIT OpenCourseWare, Prof. Dor Minzer, 18.218 Topics in Combinatorics: Analysis of Boolean Functions, Spring 2021.
License: CC BY-NC-SA 4.0 · Edition: Spring 2021 · Open the original course on OCW ↗
Organized by RedLectern, independent of MIT and not endorsed by MIT.
Per-resource rights are recorded on each resource; All-Rights-Reserved items are link-only, never mirrored.