SYLLABUS
topics (tentative).
- Algorithms, circuits- Polynomial identity testing, hitting-sets
- Hardness of parity, clique
- Expanders
- Undirected connectivity in logspace
- Pseudorandom generators
- Error correcting codes
- Hardness vs randomness
Advanced topic ideas.
- MIP equals NEXP- QIP equals PSPACE
- NQP not in ACC0
- Ramanujan graph constructions
- XOR Lemmas
- Extractors
- PCP
- Erdös-Rado, Cap-set Conjectures & matrix multiplication
Schedule.
[06Nov'23 week] List decoding. Johnson bound. Local List decoding the concatenated codes. Hardness amplification (worst- to average-case). [video25] [video26]
[30Oct'23 week] Encoding RS, WH, and their concatenated codes. Decoding them. [video23] [video24] [slide11]
[16Oct'23 week] Hardness amplification. Introduction to Error-correction. [video21] [video22] [slide10]
[09Oct'23 week] Prg. Hardness=>Derandomization. Partial derandomization applications. [video19] [video20] [slide09]
[02Oct'23 week] Pseudo-random generators (prg). [video17] [video18] [slide08]
[25Sep'23 week] Analyzing the zig-zag product in two ways. Transform any graph into an expander. [video15] [video16]
[18Sep'23 week] ** Mid-Sem **
[11Sep'23 week] Error-reduction using expanders. Graph products for explicit expanders. [video13] [video14] [slide07]
[04Sep'23 week] Random walk works. Algebraic/combinatorial expansion. Error-reduction. [video11] [video12]
[28Aug'23 week] Monotone circuits. Graph spectra, random walk, and expansion. [video09] [video10] [slide06]
[21Aug'23 week] Monotone circuit lower bounds. [video07] [video08] [slide05]
[14Aug'23 week] PIT => lower bounds. AC0, ACC0 lower bounds. [video05] [video06] [slide04]
[07Aug'23 week] Circuits. PIT. Derandomization vs circuit lower bounds. [video03] [video04] [slide02] [slide03]
[31Jul'23 week] Outline. Complexity classes. [video01] [video02] [slide01]