Princeton University
Computer Science Department

Computer Science 345
The Efficient Universe

Avi Wigderson

Spring 2006

General Information  |   Problems to Ponder   |   Handouts


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.


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.




Optional Reference:


  • 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

    Teaching Assistants: Konstantin Makarychev

    Office hours: Tue 16:00-17:00, Office: 103A CS Building

    Class Number: 42623   (COS 345/APC 345/MAT 345)