Tentative Syllabus (subject to change):
Lecture 1: Kolmogorov Complexity I:
- Randomness in Computation
- Definition of Kolmogorov Complexity (K-complexity) as a measure of randomness
- The Invariance Theorem, Undecidability of K-complexity
- Applications to Godel Incompleteness
- RE-completeness of K-complexity
Lecture 2: Kolmogorov Complexity II:
- Density of Primes
- Conditional Kolmogorov Complexity
- The Chain Rule and Symmetry of Information (SoI)
- Time-bounded Kolmogorov Complexity and the Minimum Circuit Size problem.
- Time-Hierarchies through K-complexity
Lecture 3: Kolmogorov Complexity III and One-way functions (OWFs)
- Levin-Kolmogorov Complexity
- Decision-to-Search via SoI
- One-way functions (weak, strong, worst-case)
- Random functions are very hard to Invert (via K-complexity)
Lecture 4: Hardness amplification and OWFs from K-complexity
- Hardness amplification
- One-way functions from the Hardness of Time-bounded Kolmogorov Complexity
Lecture 5: Pseudorandomness
- The Goldreich-Levin Theorem
- Randomness extractors, the Left-Over-Hash (LH) Lemma
- Towards Pseudorandom generators (PRG) from OWFs
Lecture 6: Pseudorandomness v.s. K-complexity
- Dense PRGs
- Hardness of time-bounded Kolmogorov complexity from (Dense) PRGs
- Pseudorandom generators (PRGs) from OWF
Lecture 7: Pseudorandom Functions, Learning and Range-Avoidance
- Pseudorandom function (PRF) from OWF:
- Hardness of learning from OWF
- Hardness of MCSP from OWF
- The Range-Avoidance Problem and Explicit Lowerbounds via PRF constructions.
Lecture 8: Worst-case to Average-case Reductions, NP-completeness
- Nisan-Wigderson PRGs
- Worst-case to Average-case Reductions for Time-bounded K-complexity from NW PRGs
- EXP-completeness of Levin K-complexity
- NP-completeness of conditional time-bounded Kolmogorov Complexity (outline)