CS747 - Randomized Methods in Computational Complexity (Sem I, 2018-19)

 

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.