In 1968, Lipton received his undergraduate degree in mathematics from Case Western Reserve University.
In 1973, he received his Ph.D. from Carnegie Mellon University; his dissertation, supervised by David Parnas, is entitled On Synchronization Primitive Systems.
In 1999, Lipton was elected a member of the National Academy of Engineering for the application of computer science theory to practice.
[2] If the reduction is done by treating interruptible operations as one large uninterruptible action, even with these relaxed conditions properties can be proven for a program P. Thus, correctness proofs of a parallel system can often be greatly simplified.
By bounding the "overlap" and number of queries, a secure database can be achieved.
[4] This algorithm uses a private-coin for randomization and a "virtual" choice to fool a medium adversary.
Lipton showed that randomized testing can be provably useful, given the problem satisfied certain properties.
[5] Proving correctness of a program is one of the most important problems presented in computer science.
In the area of game theory, more specifically of non-cooperative games, Lipton together with E. Markakis and A. Mehta proved[6] the existence of epsilon-equilibrium strategies with support logarithmic in the number of pure strategies.
The limited (logarithmic) size of the support provides a natural quasi-polynomial algorithm to compute epsilon-equilibria.
DeMillo, Lipton and Perlis[9] criticized the idea of formal verification of programs and argued that Chandra, Furst and Lipton[10] generalized the notion of two-party communication protocols to multi-party communication protocols.
These processes are allowed to communicate in order to arrive at a consensus on a predicate.
They studied this model's communication complexity, defined as the number of bits broadcast among all the processes.
They further applied this model to study general branching programs and obtained a time lower bound for constant-space branching programs that compute Exactly-N. We have no way to prove that the Boolean satisfiability problem (often abbreviated as SAT), which is NP-complete, requires exponential (or at least super-polynomial) time (this is the famous P versus NP problem), or linear (or at least super-logarithmic) space to solve.
However, in the context of space–time tradeoff, one can prove that SAT cannot be computed if we apply constraints to both time and space.
L. Fortnow, Lipton, D. van Melkebeek, and A. Viglas[11] proved that SAT cannot be computed by a Turing machine that takes at most O(n1.1) steps and at most O(n0.1) cells of its read–write tapes.