
Computer Science 345
The Efficient Universe
Avi Wigderson

Spring 2006

Directory
Announcements
Course Summary
We will study fundamental concepts such as Randomness, Proofs, Games,
Secrets, Knowledge, Learning and more from a computational viewpoint.
This viewpoint postulates that all observers/participants in the
definition of these concepts (be they human, machines or nature itself)
are computationally limited. This will lead us to foundational ideas,
results and problems of Computer Science: ZeroKnowledge proofs,
Cryptography,
Pseudorandom generation, Artificial Intelligence, Quantum Computing,
Escaping Mazes, Tolerating faults, adversaries and uncertainty, and of
course, the P versus NP problem.
Prerequisites
There are no formal prerequisites  we believe any student in PU can benefit
from this course, if willing to invest in it. Below is the type of helpful background
with which you may have to catch up.
The web page Is This Course for Me? may help.
In Math  we will use mostly high school level algebra,
probability and combinatorics, but in a way which will require
mathematical maturity (of the level needed e.g. the Discrete Math course [COS 341] or Linear Algebra [MAT 202, 204 or 217]).
In CS  as we deal with efficient
computation, it will help some experience with either programming or algorithms.
Reading
 Computers Ltd: What They Really Can't Do, David Harel, Oxford University Press (description)
 Computational Complexity, Christos H. Papadimitriou, Addison Wesley (description)
 DiscreteMath.com, Steven Rudich
 Introduction to the Theory of Computation, Michael Sipser, Course Technology (description)
Cryptography:
Derandomization:
Optional Reference:
 Bernard Chazelle,
Could Your iPod Be Holding the Greatest Mystery in Modern Science?
 A hip article by Chazelle on the impending algorithmic revolution in science.
 Oded Goldreich, Randomness and Computation
 Russell Impagliazzo, A Personal View of AverageCase Complexity
 David S. Johnson, NPCompleteness Columns
 Michael Kearns, Economics, Computer Science, and Policy
 Jon Kleinberg and Christos H. Papadimitriou, Computability and Complexity
 Harry R. Lewis and Christos H. Papadimitriou, The Efficiency Of Algorithms
 Geoffrey K. Pullum, Scooping the Loop Snooper, Scooping the Loop Snooper
 It is a proof of the undecidability of the Halting Problem, in verse!
Grading
50% homework and 50% exam
Administrative Information
Lectures: Fri 13:3016:20, Room: 105 CS Building
Precepts: Tue 17:0018:00, Room: 302 CS Building
Professor: Avi Wigderson, Institute for Advanced Study, Princeton.
Undergraduate Coordinator:
Donna O'Leary  410 CS Building  2581746
doleary@cs.princeton.edu
Teaching Assistants:
Konstantin Makarychev
Office hours: Tue 16:0017:00, Office: 103A CS Building
Class Number: 42623 (COS 345/APC 345/MAT 345)