SYLLABUS
topics (tentative).
- Algorithms, circuits- Polynomial identity testing, hitting-sets
- Hardness of parity
- Expanders
- Undirected connectivity in logspace
- Pseudorandom generators
- Error correcting codes
- Hardness vs randomness
Advanced topic ideas.
- MIP equals NEXP- QIP equals PSPACE
- NEXP not in ACC0
- Ramanujan graph constructions
- XOR Lemmas
- Extractors
- PCP
Schedule.
[16-Apr-2015] [pdf] Hardness amplification.
[14-Apr-2015] [pdf] Local list decoding -- WH, RM, WH-RM.
[09-Apr-2015] [pdf] List decoding RS. Local list decoding WH.
[07-Apr-2015] [pdf] Concatenated local decoder. Johnson bound.
[31-Mar-2015] [pdf] WH-RS-decoder. Local decoding -- WH, RM.
[26-Mar-2015] [pdf] Reed-Muller (RM), Concatenated codes. RS decoder.
[24-Mar-2015] [pdf] Gilbert-Varshamov, Walsh-Hadamard (WH), Reed-Solomon (RS).
[19-Mar-2015] [pdf] NEXP ⊆ P/poly implies EXP = NEXP. Hardness amplification.
[17-Mar-2015] [pdf] BPP ≠ EXP implies partial derandomization.
[12-Mar-2015] [pdf] Average-hardness vs randomness.
[10-Mar-2015] [pdf] Nisan-Wigderson design & generator.
[26-Feb-2015] [pdf] Pseudorandom generators, derandomization. Hardness notions.
[24-Feb-2015] [pdf] Strongly explicit expander constructions. Upath in L.
[12-Feb-2015] [pdf] Replacement product. Zig-zag product.
[10-Feb-2015] [pdf] Expander operations - matrix product, tensor product.
[05-Feb-2015] [pdf] Expander Chernoff bound -- saving random bits.
[03-Feb-2015] [pdf] Combinatorial expander. Cheeger's inequality.
[29-Jan-2015] [pdf] Connectivity in Logspace. Algebraic expander.
[27-Jan-2015] [pdf] Random walk and spectral gap.
[22-Jan-2015] [pdf] Monotone circuits can be approximated.
[20-Jan-2015] [pdf] Monotone circuits and cliques.
[15-Jan-2015] [pdf] Razborov-Smolensky's approximator polynomial technique.
[13-Jan-2015] [pdf] PIT implies lower bounds. Circuit lower bounds.
[08-Jan-2015] [pdf] Arthur-Merlin protocols. IP=PSPACE.
[06-Jan-2015] [pdf] Derandomization. Quantifier-based, interaction-based classes.
[01-Jan-2015] [pdf] PIT is in BPP. Arithmetic/boolean circuit model.
[30-Dec-2014] [pdf] Outline. Complexity recap.