New Jersey Governor's School 2012
Instructor: Prof. Grant Schoenebeck
Description: This course seeks to equip the participants to think like and ask questions like a theoretical computer scientist and to allow the participants experience the beauty and power of mathematics while discussing such questions as: Are there well-posed questions that no conceivable computer can solve? What types of problems are computers good at and which types can they not solve efficiently? When can flipping coins (randomness) actually help computers? How can we measure the content of data? How can we judge how good an algorithm is?
Introduction to matchings. A classic and fun application of math to
optimally matching up men and women with preference over the opposite sex.
This lecture will also introduce typical theoretical computer science methodology and terminology.
Staying to the theme of matchings in bipartite graphs, we introduce the notion of perfect matchings. We then present an algorithm to optimize the sum of the edge weights over all matchings. This algorithm uses market clearing prices.
Introduct the concept of polynomial time as a class of efficiently solvable proglem. Learn efficient algorithms for the two fundamental problems of computing flows and shortest paths. Introduce relation between max-flow and min-cut as example of duality. We also present a reduction from max flow to prefect matchings.
We exibit an algorithm for perfect matchings. We also present linear programs and the concept of duality. Finally, we show that max flow min cut is a speical case of linear programming duality.
We define computation and also define completeness and NP. We exhibit NP-completeness as a magical, common explanation to seemly unrelated yet extraordinarily important questions.
NP-completeness examples: Delve into the extreme breadth of NP-complete problems and examples of the power of reductions.
View NP-completeness from the alternate angle of proof complexity. Show how proof complexity relates to average-case hardness and approximation algorithms. Use greedy algorithm to approximate Set Cover. Using linear programming relaxations to approximate Vertex Cover.
Slides from July 9, July 10, and July 11
Show the underpinning of the theory modern cryptography and how they relate to NP-completeness. Explore Zero-knowledge proofs.
Describe why there are multiple infinities, how we can prove this, and the implication that there exist problems with no solutions. Describe and discuss Alan Turing's famous proof that the Entscheidungsproblem is not decidable which crushed the hopes of Hilbert's mathematical agenda. Discuss philosophical importance of the Universal Turning Machine to the advent of computer science.
Introduction to Kolmogorov Complexity and relations to learning. Introduce the problem of "finding hay in a haystack"--deterministically constructing object with properties of random-objects.
What is machine learning? Introduction to learning theory. Use Winnow to find monotone disjunctions. Generalize the experts algorithm and see application in boosting weak learners to strong learners, approximately solving linear programs, and hard-core sets.
Wrap-up. Questions. Recap what computer science has to say (or might say in the future) about the universe in which we live.