by Johan Håstad
Number of pages: 130
The main idea of the course has been to give the broad picture of modern complexity theory. To define the basic complexity classes, give some examples of each complexity class and to prove the most standard relations. The set of notes does not contain the amount of detail wanted from a text book. I have taken the liberty of skipping many boring details and tried to emphasize the ideas involved in the proofs. Probably in many places more details would be helpful and I would he grateful for hints on where this is the case. Most of the notes are at a fairly introductory level but some of the section contain more advanced material. This is in particular true for the section on pseudorandom number generators and the proof that IP = PSPACE. Anyone getting stuck in these parts of the notes should not be disappointed.
Home page url
Download or read it online for free here:
by Allen Downey - Green Tea Press
This book is about data structures and algorithms, intermediate programming in Python, complexity science and the philosophy of science. The book covers Graphs, Analysis of algorithms, Scale-free networks, Cellular Automata, Agent-based models, etc.
by Oded Goldreich - Cambridge University Press
The book gives the mathematical underpinnings for cryptography; this includes one-way functions, pseudorandom generators, and zero-knowledge proofs. Throughout, definitions are complete and detailed; proofs are rigorous and given in full.
This book is intended as an introductory textbook in Computability Theory and Complexity Theory, with an emphasis on Formal Languages. Its target audience is CS and Math students with some background in programming and data structures.
by Tim Roughgarden - Stanford University
The two biggest goals of the course are: 1. Learn several canonical problems that have proved the most useful for proving lower bounds; 2. Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.