Course Topics

1. Intro to Proofs
   1. Administrivia
   2. Social Choice | Arrows Theorem
2. Turing Machines
   1. Encodings, TMs, Recursive Languages
   2. TM for Palindrome and Running Time
   3. Lowerbounds for 1 Tape TMs
3. Cantor, Church, Turing, Godel
   1. Universal TMs and Halting Problem
   2. Undecidability | Halting Problem | DTIME
   3. Lowerbounds for 1 Tape TMs
4. NP Hardness
   1. 2CNF Algorithm
   2. NP Verification
   3. Cook-Levin Theorem
   4. Polynomial Hierarchy
5. Space and Circuit Complexity
   1. LSPACE | PSPACE | Completeness
   2. Circuit Model
   3. Karp - Lipton Theorem
6. Randomized Computation
   1. Randomized Algorithms Examples
   2. RP | CoRP | BPP | Robustness | Chernoffs
   3. Derandomization | Adleman's Theorem | Method of Conditional Probabilities
7. Quantum Computing