<p>Sanjeev Arora has a good set of notes he calls <a href="http://www.cs.princeton.edu/courses/archive/fall02/cs597D/">"A Theorist's Toolkit"</a></p>

CC BY-SA 3.0
2014-09-30T20:31:04.040Z
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 (http://www.cs.princeton.edu/~arora/pubs/toolkit.pdf)
rahulmehta95
CC BY-SA 2.5
2010-09-06T05:29:52.300Z
2010-09-06T05:29:52.300Z
umar
<p>There is a wiki devoted to different proof techniques: <a href="http://www.tricki.org/">http://www.tricki.org/</a> (seems to be inspired by Timothy Gowers).</p>

CC BY-SA 2.5
2010-08-20T18:44:05.457Z
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.
Kurt
CC BY-SA 2.5
2010-08-20T19:55:18.107Z
You can improve these sections, I think.
ilyaraz
CC BY-SA 2.5
2010-08-21T02:22:55.497Z
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.
Kurt
CC BY-SA 2.5
2010-08-20T17:38:33.583Z
2010-08-20T17:38:33.583Z
ilyaraz
<p>Here's another book where the chapters are more focused on proof techniques.</p>

<p>"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).</p>

<p>An "early draft" of the second edition is <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/EC_Book_2nd/draft.pdf">available here</a>.</p>

CC BY-SA 2.5
2010-08-19T16:39:17.007Z
Thanks, that looks like a really useful text--I've gone ahead and ordered myself a copy.
Kurt
CC BY-SA 3.0
2010-08-19T02:37:05.537Z
2013-09-21T00:20:58.400Z
2013-09-21T00:20:58.400Z
Ryan Williams
<p>Another techniques tome that is useful in many parts of theoretical computer science:</p>

<p>Noga Alon and Joel H. Spencer, <em>The Probabilistic Method</em> (3rd edition), Wiley, ISBN 0470170204.</p>

CC BY-SA 2.5
2010-08-19T02:47:29.227Z
2010-08-19T02:47:29.227Z
András Salamon
<p><a href="http://dx.doi.org/10.1016/S0890-5401(03)00018-X">S. Fenner, L. Fortnow, S. Kurtz, and L. Li. An oracle builder's toolkit. Information and Computation, 182(2):95-136, 2003.</a> (also available <a href="http://www.cs.uchicago.edu/~fortnow/papers/obt.pdf">from Lance's homepage</a>).</p>

<p>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.]</p>

CC BY-SA 2.5
2010-08-19T00:43:13.507Z
2010-08-19T00:43:13.507Z
Joshua Grochow
<p>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):</p>

<p><a href="http://www.calvin.edu/~rpruim/publications/gems/">http://www.calvin.edu/~rpruim/publications/gems/</a></p>

CC BY-SA 2.5
2010-08-20T03:03:36.453Z
That sounds like an interesting text, but I just tried looking it up on Amazon (http://www.amazon.com/Gems-Theoretical-Computer-Science-Sch%C3%B6ning/dp/3540644253/) and I had to do a double-take!  Must be out of print and highly prized.
Kurt
CC BY-SA 2.5
2010-08-20T02:36:41.463Z
2010-08-20T02:36:41.463Z
Dave Doty
<p>We have been starting some <a href="https://cs.meta.stackexchange.com/questions/599/reference-answers-to-frequently-asked-questions">reference questions</a> on <a href="http://cs.stackexchange.com">cs.SE</a> 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:</p>

<ul>
<li><a href="https://cs.stackexchange.com/q/1031/98">How to prove that a language is not regular?</a></li>
<li><a href="https://cs.stackexchange.com/q/265/98">How to prove that a language is not context-free?</a></li>
<li><a href="https://cs.stackexchange.com/q/2016/98">How to convert finite automata to regular expressions?</a></li>
<li><a href="https://cs.stackexchange.com/q/2789/98">Solving or approximating recurrence relations for sequences of numbers</a></li>
</ul>

<p>We also have <a href="https://cs.stackexchange.com/q/1877/98">How not to solve P=NP?</a> which is more about anti-techniques.</p>

CC BY-SA 3.0
2012-07-26T09:26:23.637Z
2013-09-30T09:39:24.393Z
2017-04-13T12:48:30.830Z
Raphael
<p>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 <a href="http://ttic.uchicago.edu/~madhurt/courses/toolkit2013/toolkit2013.html" rel="nofollow">course webpage</a>. 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.</p>

CC BY-SA 3.0
2014-09-30T20:43:23.063Z
2014-09-30T20:43:23.063Z
rahulmehta95
<p><a href="http://www.cs.rochester.edu/~lane/=companion/">The Complexity Theory Companion by Hemaspaandra and Ogihara</a>.  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:</p>

<ul>
<li>The Self-Reducibility Technique. </li>
<li>The One-Way Function Technique. </li>
<li>The Tournament Divide and Conquer Technique. </li>
<li>The Isolation Technique. </li>
<li>The Witness Reduction Technique. </li>
<li>The Polynomial Interpolation Technique. </li>
<li>The Nonsolvable Group Technique. </li>
<li>The Random Restriction Technique. </li>
<li>The Polynomial Technique.</li>
</ul>

CC BY-SA 2.5
2010-08-18T20:24:49.413Z
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.)
Kurt
CC BY-SA 2.5
2010-08-18T14:50:13.900Z
2010-08-18T14:50:13.900Z
Joshua Grochow
<p>Are there any references (online or in book form) that organize and discuss TCS theorems by proof technique?  <a href="http://rads.stackoverflow.com/amzn/click/0716710455">Garey and Johnson</a> 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.  </p>

<p>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.</p>

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

<p>In addition to chapter 3 of Garey and Johnson, here's another partial example that just occurred to me: in <a href="http://rads.stackoverflow.com/amzn/click/0387339981">Li and Vitanyi</a>, in chapter 6 they discuss the incompressibility method and give examples of how to apply the technique.</p>

CC BY-SA 2.5
2010-09-10T18:21:40.917Z
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.
Blaisorblade
CC BY-SA 2.5
2010-08-18T04:33:32.967Z
this book is great for computational complexity
http://www.cs.princeton.edu/theory/complexity/
Marcos Villagra
CC BY-SA 2.5
2010-08-18T04:34:05.633Z
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.
Suresh Venkat
CC BY-SA 2.5
2010-08-18T05:10:19.420Z
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?
Kurt
CC BY-SA 2.5
2010-08-18T06:17:57.707Z
I agree that this is far too broad. There may be interesting aspects to this question if sufficiently narrowed down.
Moritz
CC BY-SA 2.5
2010-08-18T06:54:24.827Z
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.
Kurt
<reference-request><proof-techniques>
References for TCS proof techniques
Kurt
# References for TCS proof techniques

(Asked by: username_0 on 2010-08-18)

Are there any references (online or in book form) that organize and discuss TCS theorems by proof technique? [Garey and Johnson](http://rads.stackoverflow.com/amzn/click/0716710455) 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](http://rads.stackoverflow.com/amzn/click/0387339981), in chapter 6 they discuss the incompressibility method and give examples of how to apply the technique.

**Tags:** reference-request, proof-techniques

> **Comments:**
> **username_2**: this book is great for computational complexity http://www.cs.princeton.edu/theory/complexity/  
> **username_3**: 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.  
> **username_0**: 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?  
> **username_4**: I agree that this is far too broad. There may be interesting aspects to this question if sufficiently narrowed down.  
> **username_0**: 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.  
> **username_1**: 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.  

---

## 9 answers

### Answer by username_10 on 2010-08-18. Score: 37 | Accepted answer

[The Complexity Theory Companion by Hemaspaandra and Ogihara](http://www.cs.rochester.edu/~lane/=companion/). 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.

> **Comments:**
> **username_0**: 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.)  

---

### Answer by username_8 on 2010-08-19. Score: 26

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](http://www.thi.informatik.uni-frankfurt.de/~jukna/EC_Book_2nd/draft.pdf).

> **Comments:**
> **username_0**: Thanks, that looks like a really useful text--I've gone ahead and ordered myself a copy.  

---

### Answer by username_5 on 2010-09-06. Score: 19

Sanjeev Arora has a good set of notes he calls ["A Theorist's Toolkit"](http://www.cs.princeton.edu/courses/archive/fall02/cs597D/)

> **Comments:**
> **username_6**: 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 (http://www.cs.princeton.edu/~arora/pubs/toolkit.pdf)  

---

### Answer by username_7 on 2010-08-20. Score: 16

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

> **Comments:**
> **username_0**: 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.  
> **username_7**: You can improve these sections, I think.  
> **username_0**: 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.  

---

### Answer by username_11 on 2010-08-20. Score: 15

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/>

> **Comments:**
> **username_0**: That sounds like an interesting text, but I just tried looking it up on Amazon (http://www.amazon.com/Gems-Theoretical-Computer-Science-Sch%C3%B6ning/dp/3540644253/) and I had to do a double-take!  Must be out of print and highly prized.  

---

### Answer by username_9 on 2010-08-19. Score: 13

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.


---

### Answer by username_10 on 2010-08-19. Score: 12

[S. Fenner, L. Fortnow, S. username_0z, and L. Li. An oracle builder's toolkit. Information and Computation, 182(2):95-136, 2003.](http://dx.doi.org/10.1016/S0890-5401(03)00018-X) (also available [from Lance's homepage](http://www.cs.uchicago.edu/~fortnow/papers/obt.pdf)).

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


---

### Answer by username_12 on 2012-07-26. Score: 7

We have been starting some [reference questions](https://cs.meta.stackexchange.com/questions/599/reference-answers-to-frequently-asked-questions) on [cs.SE](http://cs.stackexchange.com) 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:

* [How to prove that a language is not regular?](https://cs.stackexchange.com/q/1031/98)
* [How to prove that a language is not context-free?](https://cs.stackexchange.com/q/265/98)
* [How to convert finite automata to regular expressions?](https://cs.stackexchange.com/q/2016/98)
* [Solving or approximating recurrence relations for sequences of numbers](https://cs.stackexchange.com/q/2789/98)

We also have [How not to solve P=NP?](https://cs.stackexchange.com/q/1877/98) which is more about anti-techniques.


---

### Answer by username_6 on 2014-09-30. Score: 1

In the same spirit of Sanjeev Arora's notes that @username_5 posted, I like Madhur Tulsiani's lecture notes and exercises for his "Mathematical Toolkit" class posted at the [course webpage](http://ttic.uchicago.edu/~madhurt/courses/toolkit2013/toolkit2013.html). 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.


---

