Course Syllabus

Syllabus: 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: 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:  

Notes: Download January12.pdf

1/14

Fourier expansion and basic formulas

Video:  

Recording:  

Notes: Download January14.pdf

 

Download Week1Questions.pdf

Week1Questions.tex Download Week1Questions.tex

(O 1.1-1.4)

1/19

Probability densities and BLR linearity testing

Video:

Recording:  

Notes: Download January19.pdf

Download Week2Questions.pdf

Download Week2Questions.tex

(O 1.5-1.6)

1/21

Social choice and influences

Video:

Recording:  

Notes: Download January21.pdf

 

Download Week2Questions.pdf

Week2Questions.tex Download Week2Questions.tex

(O 2.1 - 2.3)

1/26

Noise stability and Arrow's Theorem

Video:

Recording:  

Notes: Download January26.pdf

  

Download Week3Questions.pdf

Download Week3Questions.tex

   

(O 2.4-2.5)

1/28

Spectral concentration and learning

Video:  

Recording:  

Notes: Download January28.pdf

  

Download Week3Questions.pdf

 

Week3Questions.tex Download Week3Questions.tex 

(O 3.1-3.2, 3.4)

2/2

Restrictions and the Goldreich-Levin Theorem

Video:  

Recording:  

Notes: Download February2.pdf

 

Download Week4Questions.pdf

Download Week4Questions.tex

  

(O 3.3, 3.5)

2/4

DNF formulas

Video:  

Recording:  

Notes: Download February4.pdf

 

Download Week4Questions.pdf

 

Week4Questions.tex Download Week4Questions.tex 

(O 4.1-4.3)

2/9

Linial-Mansour-Nisan Theorems

Video:  

Recording:   

Notes: Download February9.pdf

  

Download Week5Questions.pdf

Download Week5Questions.tex

   

(O 4.4-4.5)

2/11

Majority, Linear Threshold Functions, and the Central Limit Theorem

Video:  

Recording: 

 

Notes: Download February11.pdf

 

Download Week5Questions.pdf

Week5Questions.tex Download Week5Questions.tex  

(O 5.1-5.2)

2/16

Linear Threshold Functions and noise stability

Video:  

Recording:  

Notes: Download February16.pdf

  

Download Week6Questions.pdf

Download Week6Questions.tex

   

(O 5.3-5.5)

2/18

Level-1 inequality and the 2/pi Theorem

Video:  

Recording:  

Notes: Download February18.pdf

 

Download Week6Questions.pdf

Week6Questions.tex Download Week6Questions.tex  

(O 5.4, 9.1)

2/23

Bonami's Lemma and the KKL Theorem
Video:
Recording:  

Download Week7Questions.pdf

Download Week7Questions.tex

   

(O 9.2, 9.6)

2/25

Dictator Testing and the FKN Theorem

Video:

Recording:   

Notes: Download February25.pdf

   

Download Week7Questions.pdf

Week7Questions.tex Download Week7Questions.tex   

(O 7.1, 9.1)

3/2

Probabilistically checkable proofs of proximity

Video:

Recording:  

Notes: Download March2.pdf

   

Download Week8Questions.pdf

Download Week8Questions.tex

   

(O 7.2)

3/4

Constraint satisfaction problems

Video:

Recording:  

Notes: Download March4.pdf

   

Download Week8Questions.pdf

Week8Questions.tex Download Week8Questions.tex  

(O 7.3)

3/9

Håstad's hardness theorems

Video:  

Recording:  

Notes: Download March9.pdf

  

Download Week9Questions.pdf

Download Week9Questions.tex

   

(O 7.4)

3/11

The Hypercontractivity Theorem

Video:

Notes: Download March11.pdf

  

Download Week9Questions.pdf Week9Questions.tex Download Week9Questions.tex   (O 9.3, 9.4)

 

Course Summary:

Date Details Due