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.

[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]