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.
[22Sep'25 week] Error-reduction using expanders. Graph products for explicit expanders. [video13] [video14] [slide07]
[15Sep'25 week] ** Mid-Sem **
[08Sep'25 week] Random walk works. Algebraic/combinatorial expansion. Error-time trade-offs in randomized algorithms. [video11] [video12]
[01Sep'25 week] Monotone circuits. Graph spectra, random walk, and expansion. [video09] [video10] [slide06]
[25Aug'25 week] Monotone circuit lower bounds. [video07] [video08] [slide05]
[18Aug'25 week] PIT => lower bounds. AC0, ACC0 lower bounds. [video05] [video06] [slide04]
[11Aug'25 week] Circuits. PIT. Derandomization vs circuit lower bounds. [video03] [video04] [slide02] [slide03]
[04Aug'25 week] Outline. Complexity classes. [video01] [video02] [slide01]