30
$\begingroup$

Richard J. Lipton has been selected as the winner of the 2014 Knuth Prize "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.

$\endgroup$
  • 11
    $\begingroup$ Congratulations to Richard J.Lipton ! :-) $\endgroup$ – Marzio De Biasi Sep 16 '14 at 23:14
  • $\begingroup$ RJLipton blog (~5yr old) with links to his books/ research etc $\endgroup$ – vzn Sep 17 '14 at 18:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Sep 18 '14 at 4:10
  • $\begingroup$ Here's a link to the Knuth Prize Lecture: techtalks.tv/talks/… $\endgroup$ – Michael Wehar May 28 '15 at 23:29
  • 1
    $\begingroup$ There are two papers not yet mentioned here that both have over 500 citations on Google Scholar: scholar.google.com/… (Aleliunas et al., on L vs. NL, an important complexity paper) and scholar.google.com/… (De Millo et al., on why testing is perhaps better than formal proofs of correctness of programs -- controversial!) $\endgroup$ – András Salamon May 29 '15 at 20:24
34
$\begingroup$

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 (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 gives a good starting place to explore the numerous applications. An early survey with details of a number of applications was written by Lipton and Tarjan in 1980.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Saeed Sep 17 '14 at 0:51
  • 14
    $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Sep 17 '14 at 2:40
  • 3
    $\begingroup$ @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! $\endgroup$ – Sasho Nikolov Sep 17 '14 at 2:46
  • 9
    $\begingroup$ 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). $\endgroup$ – Sasho Nikolov Sep 17 '14 at 16:55
  • 3
    $\begingroup$ 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. $\endgroup$ – Saeed Sep 17 '14 at 17:25
26
$\begingroup$

Karp-Lipton Theorem states that $\mathsf{NP}$ cannot have polynomial-size boolean circuits unless the 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).
$\endgroup$
23
$\begingroup$

Random Self-Reducibility of the Permanent. Lipton showed 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.

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.

$\endgroup$
16
$\begingroup$

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 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. 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” specifications and theorems. Typically, incorrect specifications 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.

  2. R. A. DeMillo, R. J. Lipton, F. G. Sayward, Hints on Test Data Selection: Help for the Practicing Programmer.

  3. R. G. Hamlet, Testing Programs with the Aid of a Compiler.

  4. S. Berghofer, T. Nipkow, Random testing in Isabelle/HOL..

$\endgroup$
15
$\begingroup$

Schwartz - Zippel - DeMillo-Lipton 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.

$\endgroup$
  • 4
    $\begingroup$ 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). $\endgroup$ – Ashley Montanaro Sep 17 '14 at 10:41
13
$\begingroup$

Coverability in vector addition systems is EXPSPACE-hard: in R. J. Lipton, The reachability problem requires exponential space, 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, Lipton's result shows the completeness for EXPSPACE.

This result, as recounted on Lipton's blog, 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.

$\endgroup$
5
$\begingroup$

Multiparty communication complexity and the Number-on-Forehead model were introduced by Ashok K. Chandra, Merrick L. Furst and Richard J. Lipton in Multi-party Protocols, STOC 1983, doi:10.1145/800061.808737.

The multiparty model is a natural extension of 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, via a multidimensional form of Van Der Waerden's 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 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.

$\endgroup$
  • $\begingroup$ Looks very nice, thanks for following through on my suggestion. $\endgroup$ – Sasho Nikolov May 29 '15 at 17:57

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.