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.
[29Oct, 01,05,08,12,15Nov] [pdf] Error-correcting codes amplify hardness.
[08,11,22,25Oct] [pdf] Pseudorandom generator (prg) & hardness.
[04,06,08Oct] [pdf] Explicit expanders exist.
[08,10,13Sep, 01Oct] [pdf] Expansion properties.
[27,30Aug, 06Sep] [pdf] Monotone circuits are weak.
[25,27Aug] [pdf] Constant-depth circuits are weak.
[09,13,16,23Aug] [pdf] Derandomize & get a lower bound.
[02,06Aug] [pdf] Circuits, PIT.
[30Jul, 02Aug 2018] [pdf] Outline.