Course Syllabus
Syllabus: syllabus.pdf
Class Meetings: Tuesday, Thursday, 2-3:20 (CST), Zoom: 957 7043 3496
Instructor: Shravas Rao, shravas@northwestern.edu
Office hours: Tuesday, Thursday, 1-1:50 (CST), Zoom: 664 905 3980
Campuswire: https://campuswire.com/p/G56CB3734 (Code - 2967)
Textbook: Analysis-Of-Boolean-Functions-version1-01-by-Ryan-ODonnell.pdf
The following is a tentative list of topics and related references in the text .
|
Date |
Lecture Topics | Problems | Related References |
|
1/12 |
Introduction Recording: Notes: January12.pdf |
||
|
1/14 |
Fourier expansion and basic formulas Video: Recording: Notes: January14.pdf |
(O 1.1-1.4) | |
|
1/19 |
Probability densities and BLR linearity testing Video: Recording: Notes: January19.pdf |
(O 1.5-1.6) | |
|
1/21 |
Social choice and influences Video: Recording: Notes: January21.pdf |
(O 2.1 - 2.3) | |
|
1/26 |
Noise stability and Arrow's Theorem Video: Recording: Notes: January26.pdf |
(O 2.4-2.5) | |
|
1/28 |
Spectral concentration and learning Video: Recording: Notes: January28.pdf |
(O 3.1-3.2, 3.4) | |
|
2/2 |
Restrictions and the Goldreich-Levin Theorem Video: Recording: Notes: February2.pdf |
(O 3.3, 3.5) | |
|
2/4 |
DNF formulas Video: Recording: Notes: February4.pdf |
(O 4.1-4.3) | |
|
2/9 |
Linial-Mansour-Nisan Theorems Video: Recording: Notes: February9.pdf |
(O 4.4-4.5) | |
|
2/11 |
Majority, Linear Threshold Functions, and the Central Limit Theorem Video: Recording:
Notes: February11.pdf |
(O 5.1-5.2) | |
|
2/16 |
Linear Threshold Functions and noise stability Video: Recording: Notes: February16.pdf |
(O 5.3-5.5) | |
|
2/18 |
Level-1 inequality and the 2/pi Theorem Video: Recording: Notes: February18.pdf |
(O 5.4, 9.1) | |
|
2/23 |
Bonami's Lemma and the KKL Theorem
Video:
Recording:
Notes: February23.pdf
|
(O 9.2, 9.6) | |
|
2/25 |
Dictator Testing and the FKN Theorem Video: Recording: Notes: February25.pdf |
(O 7.1, 9.1) | |
|
3/2 |
Probabilistically checkable proofs of proximity Video: Recording: Notes: March2.pdf |
(O 7.2) | |
|
3/4 |
Constraint satisfaction problems Video: Recording: Notes: March4.pdf |
(O 7.3) | |
|
3/9 |
Håstad's hardness theorems Video: Recording: Notes: March9.pdf |
(O 7.4) | |
|
3/11 |
The Hypercontractivity Theorem Video: Notes: March11.pdf |
Week9Questions.pdf Week9Questions.tex | (O 9.3, 9.4) |
Course Summary:
| Date | Details | Due |
|---|---|---|