The Math Behind the Machine

New Jersey Governor's School 2011

Instructor: Dr. Grant Schoenebeck
Room: SERC 217
Elective Section: Elective A
Time: 9:15am - 10:35am

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?

Thanks

Many of the Powerpoint presentation slides were copied or modified from previous versions of the class by Troy Lee in 2010 and Ryan and Virgia Williams in 2009. I want to express my graditude for their permission to do so.

(Tentative) Schedule:

1) Introduction:

A) Stable Matchings: (Monday, June 27)

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. Slides

B) To Infinity and Beyond: (Tuesday, June 28)

Describe why there are multiple infinities, how we can prove this, and the implication that there exist problems with no solutions. Slides

C) Incomputable functions: (Wednesday, June 29)

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. Slides

2) P, NP, Completeness, and Proofs:

A) Polynomial Time Algorithms: (Thursday, June 30)

Define polynomial time algorithms to capture the notion of efficient computation. Slides

B) NP-completeness I: (Friday, July 1)

Define completeness and NP. Exhibit NP-completeness as a magical, common explanation to seemly unrelated yet extraordinarily important questions. Slides

B) NP-completeness II: (Tuesday, July 5)

NP-completeness examples: Delve into the extreme breadth of NP-complete problems and examples of the power of reductions. Slides

C) Dealing with NP-completeness--Proof Complexity, Approximation, and Average-case Hardness: (Thursday, July 7)

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.

3) Learning

A) On-line Algorithms and Experts: (Friday, July 8)

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. Slides

4) Randomness

A) Kolmogorov Complexity: (Monday, July 11)

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. Slides

B) Randomness in Computation and Communication: (Tuesday, July 12)

Introduce the notion of a randomized algorithm with Primality Testing. Show how randomness can help in computation in Polynomial Identity Testing; Introduction to communication complexity. Look at upper and lower bounds for Set Intersection problem. Show how randomness provably helps in checking equality via finger prints. Slides

5) Cryptography:

A) Cryptography: (Thursday, July 14)

Show the underpinning of the theory modern cryptography and how they relate to NP-completeness. Explore Zero-knowledge proofs. Slides

6) The Computational Universe

A) The Computational Universe: (Friday, July 15)

Wrap-up. Questions. Recap what computer science (or might say in the future) about the universe in which we live. Slides