Gems of Theoretical Computer Science by Uwe SchöningGems of Theoretical Computer Science by Uwe Schöning

Gems of Theoretical Computer Science

byUwe Schöning, R. Pruim, Randall J. Pruim

Paperback | September 19, 2011

Pricing and Purchase Info

$163.08 online 
$193.50 list price save 15%
Earn 815 plum® points

Prices and offers may vary in store


In stock online

Ships free on orders over $25

Not available in stores


While I was visiting Boston University during the 1996-97 academic year, I noticed a small book, written in German, on a shelf in Steve Homer's office. Curious, I borrowed it for my train ride home and began reading one of the chapters. I liked the style and format of the book so much that over the course of the next few months I frequently found myself reaching for it and working through one chapter or another. This was my introduction to Peden der Theoretischen Informatik. A few of my colleagues had also seen the book. They also found it inter­ esting, but most of them did not read German well enough to read more than small portions of it enjoyably. I hope that the English version will rectify this situation, and that many will enjoy (and learn from) the English version as much as I enjoyed the German version. The front matter of this book says that it has been "translated, revised, and expanded." I should perhaps say a few words about each of these tasks. In translating the book, I have tried as much as possible to retain the feel of the original, which is somewhat less formal and impersonal than a typical text book yet relatively concise. I certainly hope that the "pleasure of the pursuit of understanding" has not gotten lost in the translation.
Title:Gems of Theoretical Computer ScienceFormat:PaperbackDimensions:320 pagesPublished:September 19, 2011Publisher:Springer-Verlag/Sci-Tech/TradeLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:3642643523

ISBN - 13:9783642643521


Table of Contents

The Priority Method.- Hilbert's Tenth Problem.- LOOP Programs.- Bottom Drawers for Resolution Proofs.- The Spectral Problem.- Kolmogorov Complexity.- Circuits for the Parity Function.- PAC Learning.- The Berman-Hartmanis Conjecture.- Collaborating Hierarchies.- Equivalence of Branching Programs.- Craig Interpolants.- Probability Amplification.- Interactive Proof Systems.- Zero Knowledge.- Graph Isomorphism.- Superconcentrations.- Pebble Game.