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.