Computability, Zero-Knowledge & Differential Privacy
Automata, cryptographic hardness, interactive proofs, and privacy guarantees
Connects Michael Sipser's MIT theory of computation and Christof Paar's cryptography foundations with Turing Award lectures by Silvio Micali, Leslie Valiant, and Cynthia Dwork.
Curriculum sequence
6
1. Introduction, Finite Automata, Regular Expressions
Establishes formal models of computation, finite automata, and mathematical proof structure.
2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
Introduces nondeterminism and closure constructions that foreshadow NP verification.
Lecture 1: Introduction to Cryptography by Christof Paar
Bridges abstract hardness to adversarial security models and symmetric ciphers.
Proofs, Knowledge, and Computation: Zero-Knowledge Interactive Systems
Revolutionizes mathematical proof through randomized interaction and zero-knowledge secrecy.
What Needs to Be Added to Machine Learning? PAC Learning and Reasoning
Unifies computational complexity with statistical learnability via the PAC framework.
Differential Privacy: Fundamentals to Forefront
Proves sharp mathematical bounds on statistical inference without leaking individual records.