Tentative list of topics for HDX and Codes School

Coding Theory

Day 1 [28 April] Introduction
- Hour 1 - Definitions - codes, rate, distance, basic bounds, local decoding, local testing, RS codes
- Hour 2 - Berlekamp-Welch Decoder, RM codes, RM codes are locally decodable + setup for RM codes are locally testable
Day 2 [29 April]: Expander codes and LTCs
- Hour 1 - Expander based codes - Tanner/Sipser-Spielman, linear time decoding
- Hour 2 - RM codes are locally testable
Day 3 [30 April] LTCs and decoding
- Hour 1 - BHR - random LDPC codes are not locally testable, intro to the c^3 LTCs
- Hour 2 - Decoding beyond half the min distance - Johnson bound, Sudan’s algorithm for list decoding RS codes, sketch of Guruswami-Sudan’s algorithm
Day 4 [1 May] Expander-based codes
- Hour 1 - more expander techniques, AEL + applications
- Hour 2 - Univariate multiplicity codes and list decoding up to capacity, possibly the new list size bounds

High-dimensional Expanders

Day 1 [28 April] (Lectures 1/2): Expanders
- Spectral and edge expansion
- Expander-mixing or Cheeger (easy direction)
- Constructions (without proof)
- Random-walks/mixing-time + handling weighted graphs.
Day 2 [29 April] (Lectures 3/4): Spectral HDX
- Spectral HDX definitions (simplicial/poset view + distributional view)
- dense examples + failure of random complexes,
- (Partite?) Trickling-down theorem
- Intro to down-up operators + high order random walks,
- State Alev-Lau Thm & preliminaries for proof.
Day 3 [30 April] (Lectures 5/6): Spectral HDX (Continued)
- Proof of Alev-Lau (Alev-Rao/Liu version via chain rule for variance)
- Sampler graphs (Spectral + Chernoff bounds (state only))
- Boolean Analysis on HDX (Swap walks + Approximate Efron-Stein Decompositions)
Day 5 [2 May] (Lectures 7/8): HDX and CSPs
- Algorithms for k-CSPs on HDX (+ connections to codes?)
- Integrality gaps from Co-boundary expansion

Chain Complexes and Codes