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 

Week1Questions.pdf

Week1Questions.tex

(O 1.1-1.4)

1/19

Probability densities and BLR linearity testing

Video:

Recording:  

Notes: January19.pdf

Week2Questions.pdf

Week2Questions.tex

(O 1.5-1.6)

1/21

Social choice and influences

Video:

Recording:  

Notes: January21.pdf 

Week2Questions.pdf

Week2Questions.tex

(O 2.1 - 2.3)

1/26

Noise stability and Arrow's Theorem

Video:

Recording:  

Notes: January26.pdf  

Week3Questions.pdf

Week3Questions.tex    

(O 2.4-2.5)

1/28

Spectral concentration and learning

Video:  

Recording:  

Notes: January28.pdf  

Week3Questions.pdf 

Week3Questions.tex 

(O 3.1-3.2, 3.4)

2/2

Restrictions and the Goldreich-Levin Theorem

Video:  

Recording:  

Notes: February2.pdf 

Week4Questions.pdf

Week4Questions.tex   

(O 3.3, 3.5)

2/4

DNF formulas

Video:  

Recording:  

Notes: February4.pdf 

Week4Questions.pdf 

Week4Questions.tex 

(O 4.1-4.3)

2/9

Linial-Mansour-Nisan Theorems

Video:  

Recording:   

Notes: February9.pdf  

Week5Questions.pdf

Week5Questions.tex    

(O 4.4-4.5)

2/11

Majority, Linear Threshold Functions, and the Central Limit Theorem

Video:  

Recording: 

 

Notes: February11.pdf 

Week5Questions.pdf

Week5Questions.tex  

(O 5.1-5.2)

2/16

Linear Threshold Functions and noise stability

Video:  

Recording:  

Notes: February16.pdf  

Week6Questions.pdf

Week6Questions.tex    

(O 5.3-5.5)

2/18

Level-1 inequality and the 2/pi Theorem

Video:  

Recording:  

Notes: February18.pdf 

Week6Questions.pdf

Week6Questions.tex  

(O 5.4, 9.1)

2/23

Bonami's Lemma and the KKL Theorem
Video:
Recording:  
Notes: February23.pdf  

Week7Questions.pdf

Week7Questions.tex    

(O 9.2, 9.6)

2/25

Dictator Testing and the FKN Theorem

Video:

Recording:   

Notes: February25.pdf   

Week7Questions.pdf

Week7Questions.tex   

(O 7.1, 9.1)

3/2

Probabilistically checkable proofs of proximity

Video:

Recording:  

Notes: March2.pdf   

Week8Questions.pdf

Week8Questions.tex    

(O 7.2)

3/4

Constraint satisfaction problems

Video:

Recording:  

Notes: March4.pdf   

Week8Questions.pdf

Week8Questions.tex  

(O 7.3)

3/9

Håstad's hardness theorems

Video:  

Recording:  

Notes: March9.pdf  

Week9Questions.pdf

Week9Questions.tex    

(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