Computational Geometry pages by Jeff Erickson
Bibliography and syllabus for a one semester course on Interactive Proofs (IP).
And in case you wanted a simpler explanation of IP and PCP, go to the Arthur-Merlin site at UChicago for a cartoon-based explanation. Who said that complexity can't be fun!!.
Some references on lower bounds on NP-Complete Problems.
Some references to literature on complexity theory.
Parameterized complexity home page.
References to P-complete problems and a (slightly out of date) tech report A Compendium of Problems Complete for P, by Raymond Greenlaw, H. James Hoover, and Walter L. Ruzzo.
Probabilistic Checking of Proofs and Hardness of Approximation Problems by Sanjeev Arora.
The Quantum Complexity Reference Collection.
special interest group on complexity of the German computer science society.
A very nice collection of links on graph theory is here.
Analysis of Algorithms Home Page by P. Flajolet and H. Prodinger
A compendium of NP Optimization Problems by P. Crescenzi and V. Kahn.
The Travelling Salesman Problem Bibliography.
Survey paper on Randomized Algorithms: On Randomization in Sequential and Distributed Algorithms, by Rajiv Gupta, Scott A. Smolka, and Shaji Bhasar.
References (including software pointer) on the Maximal Common Subgraph (MCS) algorithm problem.
A report containing a review of various string matching algorithms by Graham A. Stephen.
Literature on realistic parallel algorithms by Silvia Goetz
A Priority Queues Web Page by Lee Killough
special interest group on parallal and distributed algorithms of the German computer science society and their page on conferences, announcement, etc.