|
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: Zero-Knowledge proofs,
Cryptography,
Pseudo-random 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 Average-Case Complexity
- David S. Johnson, NP-Completeness 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:30-16:20, Room: 105 CS Building
Precepts: Tue 17:00-18:00, Room: 302 CS Building
Professor: Avi Wigderson, Institute for Advanced Study, Princeton.
Undergraduate Coordinator:
Donna O'Leary - 410 CS Building - 258-1746
doleary@cs.princeton.edu
Teaching Assistants:
Konstantin Makarychev
Office hours: Tue 16:00-17:00, Office: 103A CS Building
Class Number: 42623 (COS 345/APC 345/MAT 345)