42
$\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.

Improve this question
$\endgroup$
6
  • $\begingroup$ this book is great for computational complexity cs.princeton.edu/theory/complexity $\endgroup$
    – Marcos Villagra
    Aug 18, 2010 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, 2010 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, 2010 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, 2010 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, 2010 at 18:21

9 Answers 9

Reset to default
37
$\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.
Improve this answer
$\endgroup$
1
  • 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, 2010 at 20:24
26
$\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.

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

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

Improve this answer
$\endgroup$
1
  • $\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, 2014 at 20:31
16
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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, 2010 at 18:44
  • $\begingroup$ You can improve these sections, I think. $\endgroup$
    – ilyaraz
    Aug 20, 2010 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, 2010 at 2:22
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/

Improve this answer
$\endgroup$
1
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.

Improve this answer
$\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.]

Improve this 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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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