38
$\begingroup$

Are there any references (online or in book form) that organize and discuss TCS theorems by proof technique? Garey and Johnson do this for the various kinds of widget constructions needed for NP-completeness proofs (particularly in chapter 3 of their book), but I'm wondering if there's anything that treats proof techniques in TCS more broadly.

So for example, topics might include diagonalization, broken down further by the type of construction used; proofs by computation histories; tableau constructions; incompressibility arguments, etc. I suppose I could just chop up a standard theory of computation text and rearrange the sections, but it would be great if there is something out there that also provides some additional commentary and shows where there are commonalities between the techniques being used.

Just to be clear, since any text is going to use proofs, what I'm really interested in finding is a reference where the proof techniques themselves are the actual subject matter.

In addition to chapter 3 of Garey and Johnson, here's another partial example that just occurred to me: in Li and Vitanyi, in chapter 6 they discuss the incompressibility method and give examples of how to apply the technique.

$\endgroup$
  • $\begingroup$ this book is great for computational complexity cs.princeton.edu/theory/complexity $\endgroup$ – Marcos Villagra Aug 18 '10 at 4:33
  • $\begingroup$ this is such a broad question its scope is all of the field ! voting to close unless it can be narrowed significantly. Also, it's most likely to need to be community wiki, since there's no single definitive answer. $\endgroup$ – Suresh Venkat Aug 18 '10 at 4:34
  • 1
    $\begingroup$ I'm not looking for a list of proof techniques; I was hoping that there was already a reference of this nature out there somewhere that someone could point me to. Why not leave this open a while longer until more eyes have had a chance to see it? $\endgroup$ – Kurt Aug 18 '10 at 5:10
  • 5
    $\begingroup$ I can't help but think that I'm being misunderstood here. If the question is overly broad then there should be many possible answers. I don't know of any direct responses (obviously, or I wouldn't have asked), and maybe only a couple of partial ones. $\endgroup$ – Kurt Aug 18 '10 at 6:54
  • 1
    $\begingroup$ The problem is that proof technique in a subfield of TCS don't usually carry on to another field. I think that mathematicians usually study proofs in their courses to learn proof techniques. For instance, diagonalization doesn't apply to proving a program correct, while invariants are of little or no use in computability theory; proof techniques for amortized complexity are only relevant to that subfield. Reduction is unusual in that its applied in computability, complexity and provable cryptography. Google "theorems for free" for a technique relevant only to programs in certain languages. $\endgroup$ – Blaisorblade Sep 10 '10 at 18:21
36
$\begingroup$

The Complexity Theory Companion by Hemaspaandra and Ogihara. It's not exhaustive in terms of techniques (I imagine no such book is), but I think it qualifies as an answer to your question. Here are the titles of the chapters:

  • The Self-Reducibility Technique.
  • The One-Way Function Technique.
  • The Tournament Divide and Conquer Technique.
  • The Isolation Technique.
  • The Witness Reduction Technique.
  • The Polynomial Interpolation Technique.
  • The Nonsolvable Group Technique.
  • The Random Restriction Technique.
  • The Polynomial Technique.
$\endgroup$
  • 1
    $\begingroup$ Thanks! From the publisher's blurb, "... the book is---unlike other texts on complexity---organized by technique rather than by topic" definitely sounds like what I had in mind. (I have to admit that I don't recognize a lot of those chapter headings--this book will probably be a bit rough going for me.) $\endgroup$ – Kurt Aug 18 '10 at 20:24
25
$\begingroup$

Here's another book where the chapters are more focused on proof techniques.

"Extremal Combinatorics With Applications in Computer Science", by Stasys Jukna. It's a nice book and covers a lot of combinatorics that you may need in TCS. Of course its subject matter does not include diagonalization, tableaus, etc., but it is a collection of neat combinatorial techniques looking for an application (and at various places in the text, applications are spelled out).

An "early draft" of the second edition is available here.

$\endgroup$
  • $\begingroup$ Thanks, that looks like a really useful text--I've gone ahead and ordered myself a copy. $\endgroup$ – Kurt Aug 19 '10 at 16:39
19
$\begingroup$

Sanjeev Arora has a good set of notes he calls "A Theorist's Toolkit"

$\endgroup$
  • $\begingroup$ This class was taught at Princeton to theory grad students for several years. There's an updated version of the lecture notes from the 2005 incarnation of the course here (cs.princeton.edu/~arora/pubs/toolkit.pdf) $\endgroup$ – rahulmehta95 Sep 30 '14 at 20:31
15
$\begingroup$

The book "Gems of Theoretical Computer Science" is a good way to learn lots of different techniques (although you see each of them applied only once):

http://www.calvin.edu/~rpruim/publications/gems/

$\endgroup$
15
$\begingroup$

There is a wiki devoted to different proof techniques: http://www.tricki.org/ (seems to be inspired by Timothy Gowers).

$\endgroup$
  • $\begingroup$ Ah, that has the potential to be exactly what I was hoping for. I see that they have placeholder entries for computational complexity and algorithms, but alas, so far they are blank. $\endgroup$ – Kurt Aug 20 '10 at 18:44
  • $\begingroup$ You can improve these sections, I think. $\endgroup$ – ilyaraz Aug 20 '10 at 19:55
  • $\begingroup$ Indeed, I would probably learn a topic better by writing a new entry than by reading an existing one...a good long term project, perhaps. $\endgroup$ – Kurt Aug 21 '10 at 2:22
13
$\begingroup$

Another techniques tome that is useful in many parts of theoretical computer science:

Noga Alon and Joel H. Spencer, The Probabilistic Method (3rd edition), Wiley, ISBN 0470170204.

$\endgroup$
12
$\begingroup$

S. Fenner, L. Fortnow, S. Kurtz, and L. Li. An oracle builder's toolkit. Information and Computation, 182(2):95-136, 2003. (also available from Lance's homepage).

This is basically a survey paper on the use of genericity in constructing "designer oracles" (that is, oracles designed to have various properties). Although it's a paper, I think it qualifies as an answer to the question because it's focused on the technique and its uses, rather than any particular result. [But this is much more specific than the Complexity Theory Companion, which is why I thought it should be in a separate answer.]

$\endgroup$
7
$\begingroup$

We have been starting some reference questions on cs.SE covering typical (so far introductory) TCS problems. Besides general relevance, some answers contain methods that may not be known to every researcher, e.g. in these:

We also have How not to solve P=NP? which is more about anti-techniques.

$\endgroup$
1
$\begingroup$

In the same spirit of Sanjeev Arora's notes that @umar posted, I like Madhur Tulsiani's lecture notes and exercises for his "Mathematical Toolkit" class posted at the course webpage. In addition to Arora's excellent material his notes have a nice coverage of spectral graph theory as well as the multiplicative weights update method.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.