Schedule

Date

Topic

Pre-reading

Presenters

01/26

Hardness vs Randomness

N/A

Salil

01/28

Hardness vs Randomness

7.1-7.4 of Pseudorandomness

Salil

02/02

Intro to Expanders Lec. 1

4.1 of Pseudorandomness

Salil

02/04

Intro to Expanders Lec. 2

4.2 of Pseudorandomness

Salil

02/09

Space Bounded Computation

Ch.1 of Ted's thesis

Ted

02/11

Catalytic Computation

Ch.2 of Ted's thesis

Ted

02/18

Explicit Lossless Vertex Expanders

11.1 of Expander Graphs and Applications

Hamming code notes

Rachel

02/23

Multiplicative Extractors for Samplable Distributions Lec. 1

6.1 of Pseudorandomness

1.1 and 1.2 of Multiplicative Extractors for Samplable Distributions

Noor and Vadim

02/25

Multiplicative Extractors for Samplable Distributions Lec. 2

Sections 3.2-3.7 of Multiplicative Extractors for Samplable Distributions

Noor and Vadim

03/02

Fractional PRGs and the Polarizing Random Walk Paradigm Lec 1.

Sections 1.1-1.3 of Pseudorandom Generators from Polarizing Random Walks 

Sections 1.1-1.3 of Analysis of Boolean Functions 

Cassandra and Pranay

03/04

Fractional PRGs and the Polarizing Random Walk Paradigm Lec. 2

Section 1 of Fractional Pseudorandom Generators from Any Fourier Level 

Cassandra and Pranay

03/09

Introduction to HDX, Local Spectral Expansion and the Trickle-Down Theorem

Ch. 6 of Hopkins and Lovett

Lecture 2 by Dinur

Easton and Faris

03/11

Random walk expansion

Sections 7.1-7.3 of Hopkins and Lovett

Easton and Faris

03/23

Kaufman-Oppenheim construction of local expectral expanders lec. 1

 Sections 1-3 of  Harsha-Saptharishi 

Lecture 7 sections 2-4 by Dinur and Dikstein 

Jonathan and Prashanth

03/25

Kaufman-Oppenheim construction of local expectral expanders lec. 2

 Sections 4-5 of  Harsha-Saptharishi 

Lecture 7 section 5 by Dinur and Dikstein 

Jonathan and Prashanth

03/30

Fourier Analysis on HDX

Fourier Analysis on HDX notes

Anagha and Tejas

04/01

FKN Theorem for HDX

Anagha's notes 

Anagha and Tejas

04/06

Topological notions of High Dimensional Expansion Lec. 1

Dinur's notes

Sections 1&2 of  Coboundary and cosystolic expansion without dependence on dimension or degree

Laasya

04/08

Topological notions of High Dimensional Expansion Lec. 2

Sections 2&3 of  Coboundary and cosystolic expansion without dependence on dimension or degree

Laasya

04/13

HDX and LTCs Lec 1

Sections 2 and 3 of Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes

Yumou and Marcus

04/15

HDX and LTCs Lec 2

Section 6 of Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes

Yumou and Marcus

04/20

Ramanujan Property and Edge Universality of Random Regular Graphs Lec 1

Section 1 and 3.1-3.2 of Ramanujan Property and Edge Universality of Random Regular Graphs

Matthew and Jerry

04/22

Ramanujan Property and Edge Universality of Random Regular Graphs Lec 2

Section 1.2 of Ramanujan Property and Edge Universality of Random Regular Graphs

Matthew and Jerry

04/27

Uniform expansion bounds for Cayley graphs of SL_2(p) lec 1

Sections 3.1 and 3.2 of Bourgain-Gamburd notes by Casolo.
Optional: Group Combinatorics notes by Casolo.

Jacob and Dashiell

04/27

Uniform expansion bounds for Cayley graphs of SL_2(p) lec 2

Sections 3.3 and 3.3 of Bourgain-Gamburd notes by Casolo.
Introduction of Uniform expansion bounds for Cayley graphs of SL2(Fp) by Bourgain and Gamburd

Jacob and Dashiell

05/04

The Polynomial Freiman-Ruzsa Conjecture

Sections 2.1,2.2 and 2.5 of Additive Combinatorics and its Applications by Lovett

Aparna and Seyoon

05/06

The Polynomial Freiman-Ruzsa Conjecture

Terence Tao's Blog post on the Polynomial Freiman Ruzsa Conjecture

Aparna and Seyoon