Quotes from some published reviews of "Theory of Computational Complexity"
by D. Du and K. Ko
From CHOICE, June 2001
- ... Here one finds both a basic introduction and comprehensive treatments, especially of topics that have borne spectacular fruit in just the last
few years: circuit complexity, probabilistic complexity, interactive
proof systems, probabilistically checkable proofs, and nonapproximability.
Graduate students in the area of computer science will simply find this book
Upper-division undergraduates contemplating advanced study of this subject
can look here for an accurate picture of the field's current flavor...
From Bulletin of the London Mathematical Society, Vol. 33, 2001
- ... Part 2 ... is on nonuniform complexity ... There are good
treatments of concepts which I have always found difficult to explain,
such as paddability and the topological criteria for elusiveness...
- ... Part 3, on probabilistic complexity, moves from the seminal work
of Gill, Rabin, Soloway and Strassen in the mid-seventies to the wonderful,
more recent results on probabilistic checkable proofs.
On the way there are concise, but very well written, chapters on the
complexity of counting and interactive proof systems...
- ... Chapter 8 ... is a remarkably concise ... but comprehensive
treatment of the theory underlying the rapidly growing and important
subject of randomised algorithms.
It is very well presented, as is the following chpater on counting
classes... as far as I am aware this is the first textbook to give a
proof of the two wonderful theorems of S. Toda ...
- Overall, I recommend this book as an excellent addition to the
literature. Its coverage is both broad and deep.
There is a tremendous amount of good modern mathematics contained
in these 500 pages...Covering the whole book would take a full
one-year graduate course, but would be a very worthwhile undertaking.
From Mathematics Review, 2001k
- ... The book under review is a graduate text in computational complexity;
however, it can also be used profitably by researchers in theory. It
covers the basics and almost all of the important theorems proven
in the field ... the selection by the authors of the book under
review is excellent.