Imagine you have one normal-sized sheet of scratch paper to write on and a list of a million numbers. You read the list, making notes on your scratch paper as you go. Afterwards, someone asks "How many times did 1134547 appear in that list?" You look at your scratch paper and respond, "Between 15000 and 16000 times," and you are right. How can this be possible? You have kept track approximately of millions of things while only writing down thousands of digits. Programs which try to extract conclusions from huge quantities of data on the internet find themselves in scaled-up versions of this same situation. The volume of data being continually presented swamps the available memory, requiring new algorithmic ideas. We will discuss some of the problems and solutions in this field.

If I want to prove something to you, I can try to write down a mathematical proof to convince you. Often, though, we care about claims that don't have simple proofs. For example, if I wanted to prove that white always wins in chess, I might need quintillions of pages to enumerate every possible line of play for black. An important idea in modern computer science is to study interactive proof systems: protocols that powerful provers can use to quickly prove a claim which would otherwise take impractically long. We will discuss a number of such systems, culminating in one powerful enough to simulate an exponentially long mathematical proof. Most of the systems we discuss won't themselves be practically useful, but they are theoretically interesting and have practically important consequences.

Imagine you have one normal-sized sheet of scratch paper to write on and a list of a million numbers. You read the list, making notes on your scratch paper as you go. Afterwards, someone asks "How many times did 1134547 appear in that list?" You look at your scratch paper and respond, "Between 15000 and 16000 times," and you are right. How can this be possible? You have kept track approximately of millions of things while only writing down thousands of digits. Programs which try to extract conclusions from huge quantities of data on the internet find themselves in scaled-up versions of this same situation. The volume of data being continually presented swamps the available memory, requiring new algorithmic ideas. We will discuss some of the problems and solutions in this field.

Suppose I have several million dollars of precious artwork to sell, and a thousand collectors are interested. The collectors may behave in complicated ways--they will value different pieces of artwork differently, they may be interested only in buying several pieces as a group, and of course they may try to collude and game the system. How can I conduct an auction so that everyone is happy, I make a lot of money, and no one can game the system? I will present a number of results (some recent and some very old) concerning this and related problems in the field of mechanism design. We will discuss a variety of problems in designing auctions, elections, and efficiently allocating public goods. Some of the ideas are simple--you have probably encountered a few in your daily life--and some are rather complex and surprising.

Being able to put stuff away somewhere you can find it is important. When you are storing a billion things, it gets even more important. Many modern computer programs need to solve this problem frequently. We will discuss one way, called hashing, to arrange data in a computer (or not in a computer, if for some reason you need to store huge amounts of data by hand) so that you can find it again extremely quickly. We will cover universal hash families, FKS hashing, and cuckoo hashing.

If I want to prove something to you, I can try to write down a mathematical proof to convince you. Often, though, we care about claims that don't have simple proofs. For example, if I wanted to prove that white always wins in chess, I might need quintillions of pages to enumerate every possible line of play for black. An important idea in modern computer science is to study interactive proof systems: protocols that powerful provers can use to quickly prove a claim which would otherwise take impractically long. We will discuss a number of such systems, culminating in one powerful enough to simulate an exponentially long mathematical proof. Most of the systems we discuss won't themselves be practically useful, but they are theoretically interesting and have practically important consequences.

Thinking about sophisticated algorithm using everyday reasoning is hard. Thinking about algorithms using algorithmic reasoning is easy. Thinking about the world using everyday reasoning can get hard. Clearly, the solution is to think about the world using algorithmic reasoning. We will discuss some of the approximations and assumptions which are second nature to computer scientists but may seem strange to normal humans, including asymptotic analysis, amortization, and adversarial design.

I want to tell you some secret information in a public place where everyone can hear me. How can I do this? I will tell you.

Suppose you and a friend are talking to each other, but an eavesdropper hears every word you say. Can you still communicate without letting the eavesdropper learn anything about your conversation? Is it possible to end your emails with signatures which no one else can forge? We will discuss solutions to these and other problems of a similar flavor. The focus will be skewed towards obtaining solutions which are provably secure rather than particularly practical.

Many problems can be solved automatically by computers, but are there problems that can't be? We will discuss some limitations on the problems which can be solved by any physical machine and some interesting examples of problems that cannot be solved in general, no matter how long you are willing to spend. If time permits there may be a discussion of Godel's incompleteness theorems and their connection to the subject.

Learn how to endear yourself to friends and family with this special course on improving your skill in acting like an annoying, nitpicky snob. We cover techniques in picking apart grammatical errors, mocking minor flaws in logic, giving off an air of smug sarcasm, and other techniques for criticizing the inconsequential imperfections in the language of those around you.

Hear some crazy logical puzzles, weird physical truths, and other mind-blowing nuggets of reality that will completely change your life, make you rich and famous, and rocket you towards nirvana.