Course Syllabus
Syllabus: syllabus.pdf Download 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 Links to an external site. (Code - 2967)
Textbook: Analysis-Of-Boolean-Functions-version1-01-by-Ryan-ODonnell.pdf Download 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: |
||
|
1/14 |
Fourier expansion and basic formulas Video: Recording: |
(O 1.1-1.4) | |
|
1/19 |
Probability densities and BLR linearity testing Video: Recording: |
(O 1.5-1.6) | |
|
1/21 |
Social choice and influences Video: Recording: |
(O 2.1 - 2.3) | |
|
1/26 |
Noise stability and Arrow's Theorem Video: Recording: |
(O 2.4-2.5) | |
|
1/28 |
Spectral concentration and learning Video: Recording: |
(O 3.1-3.2, 3.4) | |
|
2/2 |
Restrictions and the Goldreich-Levin Theorem Video: Recording: |
(O 3.3, 3.5) | |
|
2/4 |
DNF formulas Video: Recording: |
(O 4.1-4.3) | |
|
2/9 |
Linial-Mansour-Nisan Theorems Video: Recording: |
(O 4.4-4.5) | |
|
2/11 |
Majority, Linear Threshold Functions, and the Central Limit Theorem Video: Recording:
|
(O 5.1-5.2) | |
|
2/16 |
Linear Threshold Functions and noise stability Video: Recording: |
(O 5.3-5.5) | |
|
2/18 |
Level-1 inequality and the 2/pi Theorem Video: Recording: |
(O 5.4, 9.1) | |
|
2/23 |
Bonami's Lemma and the KKL Theorem
Video:
Recording:
|
(O 9.2, 9.6) | |
|
2/25 |
Dictator Testing and the FKN Theorem Video: Recording: |
(O 7.1, 9.1) | |
|
3/2 |
Probabilistically checkable proofs of proximity Video: Recording: Notes: March2.pdf Download March2.pdf |
(O 7.2) | |
|
3/4 |
Constraint satisfaction problems Video: Recording: Notes: March4.pdf Download March4.pdf |
(O 7.3) | |
|
3/9 |
Håstad's hardness theorems Video: Recording: Notes: March9.pdf Download March9.pdf |
(O 7.4) | |
|
3/11 |
The Hypercontractivity Theorem Video: Notes: March11.pdf Download March11.pdf |
Week9Questions.pdf Download Week9Questions.pdf Week9Questions.tex Download Week9Questions.tex | (O 9.3, 9.4) |
Course Summary:
| Date | Details | Due |
|---|---|---|
| Tue Jan 12, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Thu Jan 14, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Tue Jan 19, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Thu Jan 21, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Assignment Week 1 Problems | due by 2pm | |
| Tue Jan 26, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Thu Jan 28, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Assignment Week 2 Problems | due by 2pm | |
| Tue Feb 2, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Thu Feb 4, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Assignment Week 3 Problems | due by 2pm | |
| Tue Feb 9, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Thu Feb 11, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Assignment Week 4 Problems | due by 2pm | |
| Tue Feb 16, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Thu Feb 18, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Assignment Week 5 Problems | due by 2pm | |
| Tue Feb 23, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Thu Feb 25, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Tue Mar 2, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Assignment Week 6 Problems | due by 2pm | |
| Thu Mar 4, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Assignment Week 7 Problems | due by 2pm | |
| Tue Mar 9, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Thu Mar 11, 2021 | Calendar Event Analysis of Boolean Functions - Lecture | 2pm to 3:30pm |
| Tue Mar 16, 2021 | Assignment Week 8 Problems | due by 2pm |
| Thu Mar 18, 2021 | Assignment Week 9 Problems | due by 2pm |