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
Given n blocks, how far can they be made to hang over the edge of a
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.