The Math Behind the Machine

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?


1) Matchings, Flows, and Markets:

A) Stable Marriage problem: (Monday, July 2)

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.

B) Perfect Matchings and the Assignment Problem: (Tuesday, July 3)

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.

Slides from July 2 and July 3

C) Flows: (Thursday, July 5)

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.

D) Perfect Matchings, Flows, Linear Programs, and Duality: (Friday, July 6)

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.

Slides from July 5 and July 6

2) Computational Complexity Theory:

A) NP-completeness: (Monday, July 9)

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.

B) Dealing with NP-completeness: (Tuesday, July 10)

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

C) Dealing with NP-completeness: (Thursday, July 12)

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

C) Cryptography: (Friday, July 13)

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

Slides from July 13

D) Infinities and Incomputable functions: (Monday, July 16)

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.

Slides from July 16

3) Randomness and Learning

A) Kolmogorov Complexity: (Tuesday, July 17)

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 from July 17

B) On-line Algorithms and Experts: (Thursday, July 19)

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.

Slides from July 20

4) The Computational Universe:

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

Slides from July 21


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.