<p>The <strong>Planar Separator Theorem</strong> states that in any planar $n$-vertex graph $G$ there exists a set of $O(\sqrt{n})$ vertices whose removal leaves the graph disconnected into at least two roughly balanced components. Moreover, such a set can be found in linear time. This (tight) result, <a href="http://epubs.siam.org/doi/abs/10.1137/0136016">proved by Lipton and Tarjan</a> (improving on a previous result by Ungar) is a powerful tool for designing algorithms on planar graphs. It gives many exact subexponential time algorithms for NP-hard problems and improved polynomial time approximation algorithms. Looking at the <a href="http://en.wikipedia.org/wiki/Planar_separator_theorem#Applications">wikipedia page</a> gives a good starting place to explore the numerous applications. An <a href="http://www.cs.princeton.edu/courses/archive/fall06/cos528/handouts/appplanar.pdf">early survey</a> with details of a number of applications was written by Lipton and Tarjan in 1980.</p>

CC BY-SA 3.0
2014-09-18T04:09:08.047Z
Ok I scaled back the claim somewhat. The 10+ years was not a joke: I stated that the direct analogue of the planar separator theorem for arbitrary minor closed families is 10+ years older than the planar separator theorem itself (the result is due to Alon, Seymour and Thomas). I should have guessed you meant other decomposition results (via path/treewidth etc). I guess we can wrap up this discussion with that.
Sasho Nikolov
CC BY-SA 3.0
2014-09-17T00:51:11.620Z
Almost all of those algorithms are based on decomposition techniques not planar separator. Also there are lots of variation of proof of that separator theorem, we should say thanks to all of those proof inventors. In the way you talked about separator we should say thanks to the guy who found numbers very first (they even didn't find small planar separator at first,they just improved old ones). Note that in decompositions we need more special kind of separators. Decomposition techniques mostly obtained by work of Robertson and Seymour, which usually works even on excluded minors.
Saeed
CC BY-SA 3.0
2014-09-17T02:40:23.217Z
@Saeed as usual, you sound strangely combative. This is community wiki, feel free to improve the answer as you see fit. I did add that they did not discover small planar separators. As far as I am aware, for each application I mention there is an example that works via the planar separator theorem (and a number of examples can be found in a 1980 survey by Lipton and Tarjan). This does not mean other tools are not needed or other methods don't exist. Lipton and Tarjan's paper predates Alon, Robertson, and Seymour's results by 10+ years.
Sasho Nikolov
CC BY-SA 3.0
2014-09-17T02:46:26.517Z
@Saeed also I cannot believe you'd suggest with a straight face that the planar separator theorem plays no more substantial role in these applications than the construction of the natural numbers. This is ridiculous!
Sasho Nikolov
CC BY-SA 3.0
2014-09-17T15:29:18.703Z
As moderator removed my latest comment I should mention that as usual you sound annoying and illogical. Instead of just improving your answer by my comment (well answer improved), you trying to do personal attacks. Everyone can edit any answer if S/He has enough knowledge about the concept, doesn't matter if it's community wiki or not (another nonsense point of your comment). I didn't edit it because I didn't like the answer. Also I'll assume 10+ is just a joke (Just look at graph minor series start publication dates), and I'll assume that you didn't see similar techniques that used before.
Saeed
CC BY-SA 3.0
2014-09-17T16:51:42.007Z
@Saeed you are showing a perfect example of a personal attack. On the other hand you being combative is hardly debatable. The community wiki comment means that while on an ordinary answer you may be concerned with others getting points for your contribution, here *no one* is getting points.
Sasho Nikolov
CC BY-SA 3.0
2014-09-17T16:55:37.400Z
In any case, let's try to be more constructive. Graph Minors I is from 1983, and is Robertson and Seymour's first paper together, so I don't see your point there. In any case I dont deny these ideas were around before: Ungar's result is from the 1950s. The point is, proving the tight bound was a landmark result, and there are a number of exact and and approximation algorithms that only need Lipton and Tarjan's theorem or decompositions that use it as a black box. The 1980 survey already gives quite a few examples (which predate Graph Minors I).
Sasho Nikolov
CC BY-SA 3.0
2014-09-17T17:20:14.583Z
I've never thought editing an answer is like a competition! I don't want to continue this discussion because seems I have to repeat every sentence. Just for a last time I'll elaborate my first comment: I didn't say that their result does not predate to others, I didn't say that their result do not solve anything. I said 1. 10+ is just a joke and I think you admit this. 2. Their result is restricted, it's just for planar graphs and even on planar graphs is restricted to quite a few classes of problems. But researchers few years later discovered techniques which are really more general ->
Saeed
CC BY-SA 3.0
2014-09-17T17:25:19.337Z
Their result is very nice (like many other nice results) but wording of this answer is in such a way that exaggerates it too much. e.g Planar separator is not really a main tool to deal with hard problem in planar graphs, at least nowadays, When there are lots of decomposition techniques for more general scenario. Also I want to stress that their work while is great but not that much great even in their time (+-5 y). Everything I said in this two comments is just repeating my previous words just because you and at least 4 others like to do personal attack.
Saeed
CC BY-SA 3.0
2014-09-16T14:23:27.673Z
2014-09-18T03:57:49.480Z
2014-09-18T03:57:49.480Z
Sasho Nikolov
<p>I'm not 100% sure if the explanation below is historically accurate. If it isn't, please feel free to edit or remove.</p>

<p><strong>Mutation testing</strong> was invented by Lipton. <a href="https://en.wikipedia.org/wiki/Mutation_testing">Mutation testing</a> can be seen as a way to measure the quality or effectiveness of a  test suite. The key idea is to inject faults into the program to be tested (i.e. to mutate the program), preferably the kinds of faults a human programmer is likely to make, and see if the test suite finds the introduced faults. A typical example of the kind of fault mutation testing would introduce could be to replace x > 0 by x &lt; 0, or replace x by x+1 or x-1.  The fraction of faults caught by the test suite is the "mutation adequacy score" of a test suite. Speaking very loosely, one can think of this as a Monte-Carlo method for computing the mutation adequacy score.</p>

<p>More abstractly one might say that mutation testing brings to the fore a symmetry or duality between a program and its test suites: not only can the test suite be used to become more confident about the correctness of a program, but conversely, a program can be used to 
gain  confidence about the quality of a test suite.</p>

<p>In the light of this duality, mutation testing is also conceptually close to <a href="https://en.wikipedia.org/wiki/Fault_injection">fault injection</a>. Both are technically similar but have different purposes. Mutation testing seeks to measure the quality of the test suite, while fault injection seeks to establish the quality of the program, usually the quality of its error handling. </p>

<p>Recently, ideas from mutation testing have been used to test (formalisations of) logical theories. To paraphrase the abstract of (4):
When developing non-trivial formalizations in a theorem prover, a considerable amount of time is devoted to “debugging” speciﬁcations and theorems. Typically, incorrect speciﬁcations or theorems are discovered during failed proof attempts. This is an expensive form of debugging. Therefore it is often useful to test conjectures before embarking on a proof. A possible way of doing this is to assign random values to the free variables of the conjecture and then evaluate it. (4) uses mutations to test the quality of the used test-case generators. </p>

<p><strong>History</strong>. From (1): The history of mutation testing can be traced back to 1971 in a student paper by Richard Lipton [...] The birth of the field can also be identified in other papers published in the late 1970s by Lipton et al. (2) as well as Hamlet (3).</p>

<ol>
<li><p><a href="http://crestweb.cs.ucl.ac.uk/resources/mutation_testing_repository/theory.php">Mutation Testing Repository: Mutation Testing Theory</a>.</p></li>
<li><p><a href="https://www.st.cs.uni-saarland.de/edu/recommendation-systems/papers/Hints_on_Test_Data_Selection-1.pdf">R. A. DeMillo, R. J. Lipton, F. G. Sayward, Hints on Test Data
Selection: Help for the Practicing Programmer</a>.</p></li>
<li><p><a href="http://dl.acm.org/citation.cfm?id=1313827">R. G. Hamlet, Testing Programs with the Aid of a Compiler</a>.</p></li>
<li><p><a href="http://www21.in.tum.de/~nipkow/pubs/sefm04.html">S. Berghofer, T. Nipkow, Random testing in Isabelle/HOL.</a>.</p></li>
</ol>

CC BY-SA 3.0
2014-09-16T09:49:02.123Z
2014-09-16T10:01:35.633Z
2014-09-16T10:01:35.633Z
Martin Berger
<p><a href="http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma"><strong>Schwartz - Zippel - DeMillo-Lipton Lemma</strong></a> is a fundamental tool in arithmetic complexity: It basically states that if you want to know whether an arithmetic circuit represents the zero polynomial, all you need is to evaluate the circuit on one input. Then you'll obtain a nonzero value with good probability if the circuit does not represent the zero polynomial. </p>

<p>This is a particularly important lemma since no polynomial-time deterministic algorithm is known for this problem.</p>

<p>The lemma is usually known as <strong>Schwartz-Zippel Lemma</strong>. A history of this lemma can be found on <a href="http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma/">Lipton's own blog</a>.</p>

CC BY-SA 3.0
2014-09-17T10:41:16.787Z
As pointed out in a comment buried at the bottom of that blog post, it's worth mentioning that an important special case of this lemma goes back to at least 1922, when it was proven by Ore (see "Finite Fields" by Lidl and Niederreiter, Theorem 6.13 and chapter notes).
Ashley Montanaro
CC BY-SA 3.0
2014-09-17T07:49:18.703Z
2014-09-17T07:49:18.703Z
Bruno
<p><a href="https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem"><strong>Karp-Lipton Theorem</strong></a> states that $\mathsf{NP}$ cannot have polynomial-size boolean circuits unless the <a href="https://en.wikipedia.org/wiki/Polynomial_hierarchy">Polynomial hierarchy</a> collapses to its second level.</p>

<p>Two implications of this theorem for complexity theory:</p>

<ul>
<li>$\mathsf{NP}$ probably has no polynomial-size boolean circuits; proving lower bounds on circuit sizes is therefore a possible approach for separating complexity classes.</li>
<li>Several results are based on this theorem to prove complexity classes separations (for instance Kannan's Theorem).</li>
</ul>

CC BY-SA 3.0
2014-09-16T08:55:09.403Z
2014-09-17T07:43:44.637Z
2014-09-17T07:43:44.637Z
Bruno
<p><strong>Random Self-Reducibility of the Permanent</strong>. <a href="http://books.google.com/books?id=_y-eBBIRBbUC&amp;lpg=PA191&amp;ots=n3Lb9pKja6&amp;lr&amp;pg=PA191#v=onepage&amp;q&amp;f=false">Lipton showed</a> that if there exist an algorithm that correctly computes the permanent of $1-1/(3n)$ fraction of all $\mathbb{F}^{n\times n}$, where $\mathbb{F}$ is a finite field of size at least $3n$, then this algorithm can be used as a black box to compute the permanent of <em>any</em> matrix with high probability. </p>

<p>The main idea is that the permanent is a low-degree polynomial, so its composition with a univariate affine function $A + xB$ is a low-degree univariate polynomial (in $x$) and can be learned exactly from a small number of values via interpolation. You can pick a random $B$ so that the composition is distributed as the permanent of a random matrix for any $x$. At $x = 0$ the univariate polynomial is just the permanent of $A$. Details can be found in <a href="http://www.cs.princeton.edu/theory/complexity/ipchap.pdf">Chapter 8 of Arora Barak</a>.</p>

<p>This algebraic approach has been extremely influential in complexity theory. Lipton's ideas  led eventually to the proof of the IP=PSPACE theorem, the proof of the PCP theorem, and to results on local error-correcting codes.</p>

CC BY-SA 3.0
2014-09-16T20:07:59.840Z
2014-09-17T17:16:50.447Z
2014-09-17T17:16:50.447Z
Sasho Nikolov
<p><strong>Coverability in vector addition systems is EXPSPACE-hard</strong>: in R. J. Lipton, <a href="http://cpsc.yale.edu/sites/default/files/files/tr63.pdf"><em>The reachability problem requires exponential space</em></a>, Research report 63, Yale University, 1976.</p>

<p>A <em>vector addition system</em> (VAS, equivalent to a Petri net) of dimension $d$ is defined as a pair $\langle v_0,A\rangle$ where $v_0$ is a vector of non-negative integers in $\mathbb{N}^d$ and $A$ is a finite set of vectors of integers included in $\mathbb{Z}^d$. A VAS defines a transition system over configurations in $\mathbb{N}^d$ where $v\to v'$ if there exists $u$ in $A$ such that $v'=v+u$ (note that no component of $v'$ can be negative).  The <em>coverability</em> problem, given a VAS and a target vector $v$ in $\mathbb{N}^d$, asks whether there exists an execution $v_0\to v_1\to\cdots\to v_n$ of the VAS such that $v_n\geq v$ for the product ordering over $\mathbb{N}^d$, i.e. $v_n(i)\geq v(i)$ for all $1\leq i\leq d$.  Combined with an EXPSPACE upper bound proven by <a href="http://dx.doi.org/10.1016/0304-3975(78)90036-1">C. Rackoff in 1978</a>, Lipton's result shows the completeness for EXPSPACE.</p>

<p>This result, as recounted on <a href="https://rjlipton.wordpress.com/2009/04/08/an-expspace-lower-bound/">Lipton's blog</a>, still provides the best known lower bound on the (seemingly? much harder) <strong>reachability</strong> problem, where one requires instead $v_n=v$. Interestingly, it was proven <em>before</em> reachability was shown decidable. The lower bound and the technique employed to prove it have been reused countless times in relation with various classes of counter systems, and indirectly for other classes of systems or logics.</p>

CC BY-SA 3.0
2014-09-17T13:56:22.233Z
2014-09-17T15:01:08.113Z
2014-09-17T15:01:08.113Z
Sylvain
<p><strong>Multiparty communication complexity</strong> and the Number-on-Forehead model were introduced by <a href="https://en.wikipedia.org/wiki/Ashok_K._Chandra">Ashok K. Chandra</a>, Merrick L. Furst and Richard J. Lipton in <em>Multi-party Protocols</em>, STOC 1983, doi:<a href="http://dx.doi.org/10.1145/800061.808737">10.1145/800061.808737</a>.</p>

<p>The multiparty model is a natural extension of <a href="https://en.wikipedia.org/wiki/Andrew_Yao">Yao</a>'s two-party model of communication complexity, where Alice and Bob each have non-overlapping halves of the input bits, and want to communicate to compute a predetermined function of the whole input.
However, extending the partition of the input bits to more parties is often not very interesting (for lower bounds, one can usually just consider the first two parties).</p>

<p>Instead, in the NOF model $k$ parties each know all except one number from a set of $k$ integers, with the number not known to the party notionally "displayed on their forehead" for the other parties to see.
Nowadays the numbers are usually required to be non-negative integers represented using at most $n$ bits.
The parties want to compute some pre-arranged Boolean function of all the numbers.
The question is: for which functions can this be done efficiently?</p>

<p>It is always possible to just send $n$ bits (for instance, by the second party telling the first party the number on its forehead).</p>

<p>The paper gives a non-trivial but essentially optimal protocol for the function Exactly-$N$, which is true when the sum of the $k$ numbers is $N$.
In particular, $k=3$ parties can determine Exactly-$N$ using $O(\sqrt{\log N})$ bits.
Since $N \le k(2^n-1)$, this is $O(\sqrt{n})$ bits.
The lower bound argument is <a href="https://en.wikipedia.org/wiki/Ramsey_theory">Ramsey-theoretic</a>, via a multidimensional form of <a href="https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem">Van Der Waerden's theorem</a>.</p>

<p>The NOF model has been used in much subsequent work in circuit complexity: multiparty communication lower bounds naturally translate into circuit lower bounds.
One classic example is the link made by Håstad and Goldmann in 1991 (doi:<a href="http://dx.doi.org/10.1007/BF01272517">10.1007/BF01272517</a> between fixed-depth threshold circuits of polynomial size, and the multiparty NOF communication complexity of the Inner Product function: a nontrivial lower bound for IP with a more than logarithmic number of parties would yield circuit size lower bounds for TC$^0$.</p>

<p>In the original paper the multiparty model was linked to branching program lower bounds, yielding that any constant-space branching program for Exactly-$N$ requires superlinear length.</p>

CC BY-SA 3.0
2015-05-29T17:57:14.907Z
Looks very nice, thanks for following through on my suggestion.
Sasho Nikolov
CC BY-SA 3.0
2015-05-29T16:59:22.077Z
2015-05-29T16:59:22.077Z
András Salamon
<p>Richard J. Lipton <a href="https://www.acm.org/media-center/2014/september/acm-awards-knuth-prize-to-pioneer-for-advances-in-algorithms-and-complexity-theory" rel="nofollow noreferrer">has been selected as the winner of the 2014 Knuth Prize</a>  "for Introduction of New Ideas and Techniques". </p>

<p>What are to your minds the main new ideas and techniques that Lipton developed?</p>

<p><em>Note. This question shall become community wiki, please put one such idea, technique or result per answer.</em></p>

CC BY-SA 3.0
2014-09-18T04:10:39.607Z
It would be nice if someone writes something about multiparty communication complexity and the number on the forehead model. I don't have time currently.
Sasho Nikolov
CC BY-SA 3.0
2015-05-28T23:29:39.133Z
Here's a link to the Knuth Prize Lecture: http://techtalks.tv/talks/knuth-prize-lecture-the-stories-behind-the-results/61363/
Michael Wehar
CC BY-SA 3.0
2015-05-29T20:24:41.113Z
There are two papers not yet mentioned here that both have over 500 citations on Google Scholar: http://scholar.google.com/scholar?cluster=10614162172866743081&hl=en&as_sdt=0,5 (Aleliunas et al., on L vs. NL, an important complexity paper) and http://scholar.google.com/scholar?cluster=8133970149534323281&hl=en&as_sdt=0,5 (De Millo et al., on why testing is perhaps better than formal proofs of correctness of programs -- controversial!)
András Salamon
CC BY-SA 3.0
2014-09-16T23:14:38.207Z
Congratulations to Richard J.Lipton ! :-)
Marzio De Biasi
CC BY-SA 3.0
2014-09-17T18:47:21.437Z
[RJLipton blog](http://rjlipton.wordpress.com/) (~5yr old) with links to his books/ research etc
vzn
CC BY-SA 4.0
2020-05-20T07:18:58.857Z
The link is updated.
Bruno
<big-list>
Lipton's most influential results
Bruno
# Lipton's most influential results

(Asked by: username_0 on 2014-09-16)

Richard J. Lipton [has been selected as the winner of the 2014 Knuth Prize](https://www.acm.org/media-center/2014/september/acm-awards-knuth-prize-to-pioneer-for-advances-in-algorithms-and-complexity-theory) "for Introduction of New Ideas and Techniques".

What are to your minds the main new ideas and techniques that Lipton developed?

*Note. This question shall become community wiki, please put one such idea, technique or result per answer.*

**Tags:** big-list
> **Comments:**
> **username_4**: Congratulations to Richard J.Lipton ! :-)  
> **username_5**: [RJLipton blog](http://rjlipton.wordpress.com/) (~5yr old) with links to his books/ research etc  
> **username_1**: It would be nice if someone writes something about multiparty communication complexity and the number on the forehead model. I don't have time currently.  
> **username_2**: Here's a link to the Knuth Prize Lecture: http://techtalks.tv/talks/knuth-prize-lecture-the-stories-behind-the-results/61363/  
> **username_3**: There are two papers not yet mentioned here that both have over 500 citations on Google Scholar: http://scholar.google.com/scholar?cluster=10614162172866743081&hl=en&as_sdt=0,5 (Aleliunas et al., on L vs. NL, an important complexity paper) and http://scholar.google.com/scholar?cluster=8133970149534323281&hl=en&as_sdt=0,5 (De Millo et al., on why testing is perhaps better than formal proofs of correctness of programs -- controversial!)  
> **username_0**: The link is updated.  

---

## 7 answers

### Answer by username_1 on 2014-09-16. Score: 35

The **Planar Separator Theorem** states that in any planar $n$-vertex graph $G$ there exists a set of $O(\sqrt{n})$ vertices whose removal leaves the graph disconnected into at least two roughly balanced components. Moreover, such a set can be found in linear time. This (tight) result, [proved by Lipton and Tarjan](http://epubs.siam.org/doi/abs/10.1137/0136016) (improving on a previous result by Ungar) is a powerful tool for designing algorithms on planar graphs. It gives many exact subexponential time algorithms for NP-hard problems and improved polynomial time approximation algorithms. Looking at the [wikipedia page](http://en.wikipedia.org/wiki/Planar_separator_theorem#Applications) gives a good starting place to explore the numerous applications. An [early survey](http://www.cs.princeton.edu/courses/archive/fall06/cos528/handouts/appplanar.pdf) with details of a number of applications was written by Lipton and Tarjan in 1980.

> **Comments:**
> **username_6**: Almost all of those algorithms are based on decomposition techniques not planar separator. Also there are lots of variation of proof of that separator theorem, we should say thanks to all of those proof inventors. In the way you talked about separator we should say thanks to the guy who found numbers very first (they even didn't find small planar separator at first,they just improved old ones). Note that in decompositions we need more special kind of separators. Decomposition techniques mostly obtained by work of Robertson and Seymour, which usually works even on excluded minors.  
> **username_1**: @Saeed as usual, you sound strangely combative. This is community wiki, feel free to improve the answer as you see fit. I did add that they did not discover small planar separators. As far as I am aware, for each application I mention there is an example that works via the planar separator theorem (and a number of examples can be found in a 1980 survey by Lipton and Tarjan). This does not mean other tools are not needed or other methods don't exist. Lipton and Tarjan's paper predates Alon, Robertson, and Seymour's results by 10+ years.  
> **username_1**: @Saeed also I cannot believe you'd suggest with a straight face that the planar separator theorem plays no more substantial role in these applications than the construction of the natural numbers. This is ridiculous!  
> **username_6**: As moderator removed my latest comment I should mention that as usual you sound annoying and illogical. Instead of just improving your answer by my comment (well answer improved), you trying to do personal attacks. Everyone can edit any answer if S/He has enough knowledge about the concept, doesn't matter if it's community wiki or not (another nonsense point of your comment). I didn't edit it because I didn't like the answer. Also I'll assume 10+ is just a joke (Just look at graph minor series start publication dates), and I'll assume that you didn't see similar techniques that used before.  
> **username_1**: @Saeed you are showing a perfect example of a personal attack. On the other hand you being combative is hardly debatable. The community wiki comment means that while on an ordinary answer you may be concerned with others getting points for your contribution, here *no one* is getting points.  
> **username_1**: In any case, let's try to be more constructive. Graph Minors I is from 1983, and is Robertson and Seymour's first paper together, so I don't see your point there. In any case I dont deny these ideas were around before: Ungar's result is from the 1950s. The point is, proving the tight bound was a landmark result, and there are a number of exact and and approximation algorithms that only need Lipton and Tarjan's theorem or decompositions that use it as a black box. The 1980 survey already gives quite a few examples (which predate Graph Minors I).  
> **username_6**: I've never thought editing an answer is like a competition! I don't want to continue this discussion because seems I have to repeat every sentence. Just for a last time I'll elaborate my first comment: I didn't say that their result does not predate to others, I didn't say that their result do not solve anything. I said 1. 10+ is just a joke and I think you admit this. 2. Their result is restricted, it's just for planar graphs and even on planar graphs is restricted to quite a few classes of problems. But researchers few years later discovered techniques which are really more general ->  
> **username_6**: Their result is very nice (like many other nice results) but wording of this answer is in such a way that exaggerates it too much. e.g Planar separator is not really a main tool to deal with hard problem in planar graphs, at least nowadays, When there are lots of decomposition techniques for more general scenario. Also I want to stress that their work while is great but not that much great even in their time (+-5 y). Everything I said in this two comments is just repeating my previous words just because you and at least 4 others like to do personal attack.  
> **username_1**: Ok I scaled back the claim somewhat. The 10+ years was not a joke: I stated that the direct analogue of the planar separator theorem for arbitrary minor closed families is 10+ years older than the planar separator theorem itself (the result is due to Alon, Seymour and Thomas). I should have guessed you meant other decomposition results (via path/treewidth etc). I guess we can wrap up this discussion with that.  

---

### Answer by username_0 on 2014-09-16. Score: 27

[**Karp-Lipton Theorem**](https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem) states that $\mathsf{NP}$ cannot have polynomial-size boolean circuits unless the [Polynomial hierarchy](https://en.wikipedia.org/wiki/Polynomial_hierarchy) collapses to its second level.

Two implications of this theorem for complexity theory:

* $\mathsf{NP}$ probably has no polynomial-size boolean circuits; proving lower bounds on circuit sizes is therefore a possible approach for separating complexity classes.
* Several results are based on this theorem to prove complexity classes separations (for instance Kannan's Theorem).


---

### Answer by username_1 on 2014-09-16. Score: 25

**Random Self-Reducibility of the Permanent**. [Lipton showed](http://books.google.com/books?id=_y-eBBIRBbUC&lpg=PA191&ots=n3Lb9pKja6&lr&pg=PA191#v=onepage&q&f=false) that if there exist an algorithm that correctly computes the permanent of $1-1/(3n)$ fraction of all $\mathbb{F}^{n\times n}$, where $\mathbb{F}$ is a finite field of size at least $3n$, then this algorithm can be used as a black box to compute the permanent of *any* matrix with high probability.

The main idea is that the permanent is a low-degree polynomial, so its composition with a univariate affine function $A + xB$ is a low-degree univariate polynomial (in $x$) and can be learned exactly from a small number of values via interpolation. You can pick a random $B$ so that the composition is distributed as the permanent of a random matrix for any $x$. At $x = 0$ the univariate polynomial is just the permanent of $A$. Details can be found in [Chapter 8 of Arora Barak](http://www.cs.princeton.edu/theory/complexity/ipchap.pdf).

This algebraic approach has been extremely influential in complexity theory. Lipton's ideas led eventually to the proof of the IP=PSPACE theorem, the proof of the PCP theorem, and to results on local error-correcting codes.


---

### Answer by username_7 on 2014-09-16. Score: 17

I'm not 100% sure if the explanation below is historically accurate. If it isn't, please feel free to edit or remove.

**Mutation testing** was invented by Lipton. [Mutation testing](https://en.wikipedia.org/wiki/Mutation_testing) can be seen as a way to measure the quality or effectiveness of a test suite. The key idea is to inject faults into the program to be tested (i.e. to mutate the program), preferably the kinds of faults a human programmer is likely to make, and see if the test suite finds the introduced faults. A typical example of the kind of fault mutation testing would introduce could be to replace x > 0 by x < 0, or replace x by x+1 or x-1. The fraction of faults caught by the test suite is the "mutation adequacy score" of a test suite. Speaking very loosely, one can think of this as a Monte-Carlo method for computing the mutation adequacy score.

More abstractly one might say that mutation testing brings to the fore a symmetry or duality between a program and its test suites: not only can the test suite be used to become more confident about the correctness of a program, but conversely, a program can be used to
gain confidence about the quality of a test suite.

In the light of this duality, mutation testing is also conceptually close to [fault injection](https://en.wikipedia.org/wiki/Fault_injection). Both are technically similar but have different purposes. Mutation testing seeks to measure the quality of the test suite, while fault injection seeks to establish the quality of the program, usually the quality of its error handling.

Recently, ideas from mutation testing have been used to test (formalisations of) logical theories. To paraphrase the abstract of (4):
When developing non-trivial formalizations in a theorem prover, a considerable amount of time is devoted to “debugging” speciﬁcations and theorems. Typically, incorrect speciﬁcations or theorems are discovered during failed proof attempts. This is an expensive form of debugging. Therefore it is often useful to test conjectures before embarking on a proof. A possible way of doing this is to assign random values to the free variables of the conjecture and then evaluate it. (4) uses mutations to test the quality of the used test-case generators.

**History**. From (1): The history of mutation testing can be traced back to 1971 in a student paper by Richard Lipton [...] The birth of the field can also be identified in other papers published in the late 1970s by Lipton et al. (2) as well as Hamlet (3).

1. [Mutation Testing Repository: Mutation Testing Theory](http://crestweb.cs.ucl.ac.uk/resources/mutation_testing_repository/theory.php).
2. [R. A. DeMillo, R. J. Lipton, F. G. Sayward, Hints on Test Data
   Selection: Help for the Practicing Programmer](https://www.st.cs.uni-saarland.de/edu/recommendation-systems/papers/Hints_on_Test_Data_Selection-1.pdf).
3. [R. G. Hamlet, Testing Programs with the Aid of a Compiler](http://dl.acm.org/citation.cfm?id=1313827).
4. [S. Berghofer, T. Nipkow, Random testing in Isabelle/HOL.](http://www21.in.tum.de/~nipkow/pubs/sefm04.html).


---

### Answer by username_0 on 2014-09-17. Score: 16

[**Schwartz - Zippel - DeMillo-Lipton Lemma**](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma) is a fundamental tool in arithmetic complexity: It basically states that if you want to know whether an arithmetic circuit represents the zero polynomial, all you need is to evaluate the circuit on one input. Then you'll obtain a nonzero value with good probability if the circuit does not represent the zero polynomial.

This is a particularly important lemma since no polynomial-time deterministic algorithm is known for this problem.

The lemma is usually known as **Schwartz-Zippel Lemma**. A history of this lemma can be found on [Lipton's own blog](http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma/).

> **Comments:**
> **username_8**: As pointed out in a comment buried at the bottom of that blog post, it's worth mentioning that an important special case of this lemma goes back to at least 1922, when it was proven by Ore (see "Finite Fields" by Lidl and Niederreiter, Theorem 6.13 and chapter notes).  

---

### Answer by username_9 on 2014-09-17. Score: 13

**Coverability in vector addition systems is EXPSPACE-hard**: in R. J. Lipton, [*The reachability problem requires exponential space*](http://cpsc.yale.edu/sites/default/files/files/tr63.pdf), Research report 63, Yale University, 1976.

A *vector addition system* (VAS, equivalent to a Petri net) of dimension $d$ is defined as a pair $\langle v\_0,A\rangle$ where $v\_0$ is a vector of non-negative integers in $\mathbb{N}^d$ and $A$ is a finite set of vectors of integers included in $\mathbb{Z}^d$. A VAS defines a transition system over configurations in $\mathbb{N}^d$ where $v\to v'$ if there exists $u$ in $A$ such that $v'=v+u$ (note that no component of $v'$ can be negative). The *coverability* problem, given a VAS and a target vector $v$ in $\mathbb{N}^d$, asks whether there exists an execution $v\_0\to v\_1\to\cdots\to v\_n$ of the VAS such that $v\_n\geq v$ for the product ordering over $\mathbb{N}^d$, i.e. $v\_n(i)\geq v(i)$ for all $1\leq i\leq d$. Combined with an EXPSPACE upper bound proven by [C. Rackoff in 1978](http://dx.doi.org/10.1016/0304-3975(78)90036-1), Lipton's result shows the completeness for EXPSPACE.

This result, as recounted on [Lipton's blog](https://rjlipton.wordpress.com/2009/04/08/an-expspace-lower-bound/), still provides the best known lower bound on the (seemingly? much harder) **reachability** problem, where one requires instead $v\_n=v$. Interestingly, it was proven *before* reachability was shown decidable. The lower bound and the technique employed to prove it have been reused countless times in relation with various classes of counter systems, and indirectly for other classes of systems or logics.


---

### Answer by username_3 on 2015-05-29. Score: 7

**Multiparty communication complexity** and the Number-on-Forehead model were introduced by [Ashok K. Chandra](https://en.wikipedia.org/wiki/Ashok_K._Chandra), Merrick L. Furst and Richard J. Lipton in *Multi-party Protocols*, STOC 1983, doi:[10.1145/800061.808737](http://dx.doi.org/10.1145/800061.808737).

The multiparty model is a natural extension of [Yao](https://en.wikipedia.org/wiki/Andrew_Yao)'s two-party model of communication complexity, where Alice and Bob each have non-overlapping halves of the input bits, and want to communicate to compute a predetermined function of the whole input.
However, extending the partition of the input bits to more parties is often not very interesting (for lower bounds, one can usually just consider the first two parties).

Instead, in the NOF model $k$ parties each know all except one number from a set of $k$ integers, with the number not known to the party notionally "displayed on their forehead" for the other parties to see.
Nowadays the numbers are usually required to be non-negative integers represented using at most $n$ bits.
The parties want to compute some pre-arranged Boolean function of all the numbers.
The question is: for which functions can this be done efficiently?

It is always possible to just send $n$ bits (for instance, by the second party telling the first party the number on its forehead).

The paper gives a non-trivial but essentially optimal protocol for the function Exactly-$N$, which is true when the sum of the $k$ numbers is $N$.
In particular, $k=3$ parties can determine Exactly-$N$ using $O(\sqrt{\log N})$ bits.
Since $N \le k(2^n-1)$, this is $O(\sqrt{n})$ bits.
The lower bound argument is [Ramsey-theoretic](https://en.wikipedia.org/wiki/Ramsey_theory), via a multidimensional form of [Van Der Waerden's theorem](https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem).

The NOF model has been used in much subsequent work in circuit complexity: multiparty communication lower bounds naturally translate into circuit lower bounds.
One classic example is the link made by Håstad and Goldmann in 1991 (doi:[10.1007/BF01272517](http://dx.doi.org/10.1007/BF01272517) between fixed-depth threshold circuits of polynomial size, and the multiparty NOF communication complexity of the Inner Product function: a nontrivial lower bound for IP with a more than logarithmic number of parties would yield circuit size lower bounds for TC$^0$.

In the original paper the multiparty model was linked to branching program lower bounds, yielding that any constant-space branching program for Exactly-$N$ requires superlinear length.

> **Comments:**
> **username_1**: Looks very nice, thanks for following through on my suggestion.  

---

