Great Ideas in Theoretical Computer Science Lectures 16-19
Tuesday, May 27th, 2008In the next-to-last GITCS installment, we cover some of the greatest hits of the 70’s and 80’s.
- Lecture 16: Private-Key Cryptography
- Lecture 17: Public-Key Cryptography
- Lecture 18: Cryptographic Protocols (including: how computer scientists date!)
- Lecture 19: Interactive Proofs / Machine Learning
(Something tells me Lecture 18 is going to get more hits than the other three combined…)
The course itself ended two weeks ago; last week was the final exam. Thanks so much to all of my students for signing up for a brand-new course, asking probing questions, enduring my excruciating jokes, and doing a fantastic job with the notes. (Of course, thanks also to my eagle-eyed readers for spotting errors.) Thanks above all to my TA, Yinmeng Zhang, who went way beyond her job description to work with students individually, tell me when I was being a doofus, etc. Because of the input of everyone who participated, this course will be better when I teach it the second time around.
Also, for anyone who might want to teach a similar course, the recipe is simple (much simpler than I expected, actually):
- Start with a standard, off-the-shelf, undergraduate computability and complexity theory course.
- Cut out the most boring parts, like pushdown automata, context-free grammars, and 105000 NP-completeness reductions. (Yes, I know these things can be taught in a non-boring way, but why make it hard on yourself?)
- Fill in the gaps with more interesting material, like zero-knowledge proofs, computational learning theory, or quantum computing.
- Add a pinch (to taste) of mindblowing results that can’t be covered in detail, like the PCP Theorem, the independence of the Continuum Hypothesis, or cosmological limits on computation.
Serves 10-100.