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 indispensable. 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.