Course Description: What can be computed efficiently? Not just by the computers on our desktops today, but by hypothetical computers with access to truly random sources, all knowing provers, and with information stored in electron spin, harnessing quantum effects?

We will look at some of the exciting topics and techniques developed to address this question, along the way covering clever algorithms, machine learning, cryptography, the power of randomness, quantum computing and the deep P vs. NP question.

June 28: Overhang
(pdf)---
Given n blocks, how far can they be made to hang over the edge of a
table top?

References: The original paper
Overhang by Paterson and Zwick showing some awesome constructions.
A follow up paper Maximum Overhang
showing these constructions are optimal.

June 30: Stable Marriage (pdf)---Is it possible to arrange marriages in such a way that no boy and girl prefer each other to the one they married?

July 2: Online Learning (pdf)---Incoming email must be classified as spam/not spam. After each email, we are told if we classified it correctly. Can we put an upper bound on the total number of mistakes we will make? We will look at the winnow algorithm for learning an unknown disjunction.

July 5: Randomness (pdf)---What is randomness? When is a deck of cards well mixed and how many shuffles does it take to do it? The use of randomness in algorithms and the ever shortening list of problems with efficient randomized algorithms and without efficient deterministic ones.

July 6: Randomness II
(pdf)---The end of the Randomness lecture,
polynomial identity testing problem.

P vs. NP(pdf)---Introduction
to one of the most important open questions in mathematics. If a
problem has a solution that can be efficiently verified, can we also
efficiently find that solution?

July 9: Guest Lecture Guy Rothblum: Digital Envelopes, Zero Knowledge, and Other Wonders of Modern Cryptography (ppt)--- How computational complexity enables digital security and privacy.

July 12: Communication Complexity (pdf)---How many bits must Alice and Bob exchange in order to arrange a date? We will also look at the benefit of randomness in protocols to check if two numbers are equal.

July 13: More about NP (pdf)---A survey of some NP complete problems through the P vs. NP game show.

July 15: Even more NP (pdf)---The first NP-complete problem and an example of a reduction. How to cope with NP-hardness: approximation algorithms and the traveling salesman problem with triangle inequality.

July 16: Game Theory (pdf)---The 2/3 of average game, Rock, Paper, Scissors, and Iocaine powder introduce Nash Equilibria and the complexity of finding them.

July 19: Quantum Computing and Beyond (pdf)---Basics of quantum computation: qubits, operations, and measurements. How entanglement differs from classical correlation. What other computational models does physics offer? Soap bubble computing, relativity computing, and time travel computing. The presentation for the second part follows the wonderful survey by Scott Aaronson, NP-complete problems and physical reality.

DiscreteMath.com: An introductory course given by Steven Rudich at Carnegie Mellon with some of the same topics.

Knowledge, Creativity and P versus NP: An article by Avi Wigderson on the broader impact of the P versus NP question.

The Efficient Universe: A course given by Avi Wigderson.

The Computational Universe: A non-majors course given by Sanjeev Arora.

Computational Complexity Summer Program: A series of lectures for undergraduates given by Alexis Maciel and David Mix Barrington for the IAS/Park City Summer Math Program.

NP-completeness columns : A column run by David Johnson showcasing the diversity of NP-complete problems.

The Complexity Zoo: A compilation of every complexity class under the sun by Scott Aaronson.

Algorithms: A very readable book by Dasgupta, Papadimitriou, and Vazirani with more coverage of many of the things we discuss. A draft copy is available at the link.

Gower's Weblog: blog by Timothy Gowers

Godel's Lost Letter and P=NP: blog by Dick Lipton

Shtetl-Optimized: blog by Scott Aaronson

Math Overflow: A great site for posting and answering questions.

SciRate: Interface to arXiv with collaborative ranking system. Mostly active for quantum papers.

ECCC: A specialized archive for TCS papers.