SYLLABUS
Fundamentals.
- Turing machine- Non-deterministic time
- Time/Space Hierarchy
- Space complexity
- Counting complexity classes
- Randomization
- Circuits
- Interaction
Advanced Topic ideas.
- you choose a paper/result- Matiyasevich's proof of Hilbert's 10th problem
- Reingold's graph reachability in logspace
- AKS' primality test
- Hastad's parity is not in AC_0
- Williams' NEXP is not in ACC_0
- Razborov-Rudich's natural proof barrier
- Aaronson-Wigderson's algebrization barrier
Schedule.
[09,13Nov-2017] [pdf] Interaction & Circuits.
[30Oct, 02,06Nov-2017] [pdf] Probabilistic TM.
[23,26,30Oct-2017] [pdf] Counting vs Hierarchy.
[09,12,16Oct-2017] [pdf] Counting classes.
[14Sep, 05,09Oct-2017] [pdf] Polynomial hierarchy.
[04,07,11Sep-2017] [pdf] Space complexity.
[28,31Aug-2017] [pdf] Oracle, Relativization.
[21,24,28Aug-2017] [pdf] Hierarchy theorems.
[21Aug-2017] [pdf] co-Classes, EXP-classes.
[17Aug-2017] [pdf] Reduction.
[14,17Aug-2017] [pdf] Nondeterminism.
[07,10Aug-2017] [pdf] Computability, Complexity Classes.
[03,07Aug-2017] [pdf] Formalizing Problems, Machines, Time & Space.
[31Jul-2017] [pdf] Introduction & outline to Complexity.