law. On The Computational Power of DNA (2009)
Dan Boneh, Christopher Dunworth, Richard J. Lipton, Sgall Y
States Code) governs the making of photocopies or other reproductions of copyrighted materials. Under certain conditions specified in the law, libraries and archives are authorized to furnish a...
Reduction: A Method of Proving Properties of Parallel Programs (2009)
B. Wegbriet, Richard J. Lipton
When proving that a parallel program has a given property it is often convenient to assume that a statement is indivisible, i.e. that the statement cannot be interleaved with the rest of the program....
34 Hintson Test Data Selection: Help forthe Practicing Programmer (2009)
Richard A. Demillo, Richard J. Lipton
reliability deals with tentative methodologies and underdeveloped techniques; hence it is not surprising that the programning staff responsible for debugging a large piece of software often feels...
Abstract Simple with Strategies for Large Zero-Sum Games Applications to (2009)
Von Neumann’s Min-Max Theorem guarantees that each player of a zero-sum matrix game hss an optimal mixed strategy. We show that each player has a near-optimal mixed strategy that chooses uniformly...
Professional Experience (2008)
Parikshit Gopalan, Advisor Prof, Richard J. Lipton, Host Prof, Venkatesan Guruswami
On the Complexity of SAT (Revised) (2008)
We show 1 that non-deterministic time NT IME(n) is not contained in deterministic time n √ 2−ɛ and polylogarithmic space, for any ɛ> 0. This implies that (infinitely often) satisfiability...
Reports and Articles Social Processes and Proofs of Theorems and Programs (2008)
Richard J. Lipton, Alan J. Perlis
It is argued that formal verifications of programs, no matter how obtained, will not play the same key role in the development of computer science and software engineering as proofs do in...
Improved Bounds for Learning Symmetric Juntas (2008)
Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
We consider a fundamental problem in computational learning theory: learning in the presence of irrelevant information. In particular we are interested in learning an arbitrary boolean function of n...
On the Complexity of Hilbert’s 17th Problem (2008)
Nikhil R. Devanur, Richard J. Lipton, Nisheeth K. Vishnoi
Abstract. Hilbert posed the following problem as the 17th in the list of 23 problems in his famous 1900 lecture: Given a multivariate polynomial that takes only non-negative values over the reals,...
Reports and Articles Social Processes and Proofs of Theorems and Programs (2008)
Richard J. Lipton, Alan J. Perlis
It is argued that formal verifications of programs, no matter how obtained, will not play the same key role in the development of computer science and software engineering as proofs do in...
Descartes Rule of Signs (2008)
Saugata Basu, Nayantara Bhatnagar, Richard J. Lipton, Parikshit Gopalan
We study the sparsity of real polynomials that sign represent parity on ¢ variables, each of which takes values from some finite subset £ of integers. While the degree of such polynomials has been...
Parikshit Gopalan, Advisor Prof, Richard J. Lipton, J Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton
theory, Boolean function complexity.
Parikshit Gopalan, Advisor Prof, Richard J. Lipton, J Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton
theory, Boolean function complexity.
The Complexity of the A B C Problem Resolved (2007)
Jin-Yi Cai, Richard J. Lipton, Yechezkel Zalcstein
this paper, we extend previous results in two directions. First, we allow infinite systems, where even decidability is not clear, and second, we consider semigroups as well. On the other hand, since...
Richard J. Lipton, Anastasios Viglas
that non-deterministic time NT IME(n) is not contained in deterministic time n # 2-# and polylogarithmic space, for any #> 0. This implies that (infinitely often) satisfiability cannot be solved...
Communication Complexity of Key Agreement on Small Ranges (2007)
Jin-yi Cai, Richard J. Lipton, Luc Longpré, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar, ...
. We study a variation on classical key-agreement and consensus problems in which the key space S is the range of a random variable that can be sampled. We give tight upper and lower bounds of dlog 2...
Effect of Operators on Straight Line Complexity (Extended Abstract) (2007)
We show that certain explicit operators must vastly increase the straight line complexity of certain polynomials.
The Degree of Threshold mod 6 and Diophantine Equations (2007)
Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton
We continue the study of the degree of polynomials representing threshold functions modulo 6 initiated by Barrington et al.[1]. We use the framework established in [4] relating representations by...
Jin-yi Cai, Richard J. Lipton, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar
We study a variation on classical key-agreement and consensus problems in which the key space S is the range of a random variable that can be sampled. We give tight upper and lower bounds of dlog 2...
Information Processing Letters (2007)
On proving that a graph has no large clique: A connection with Ramsey theory
A Local-Global Principle for Diophantine Equations (Extended Abstract) (2007)
Richard J. Lipton, Nisheeth Vishnoi
Abstract. We observe the following global-local principle for Diophantine equations: If an equation f(x1,..., xt) ∈ Z[x1,..., xt] = p can be solved efficiently for a dense set of primes p, then one...
Randomized Time-Space Tradeoffs for Directed Graph Connectivity (2007)
Parikshit Gopalan, Richard J. Lipton, Aranyak Mehta
We present a spectrum of randomized time-space tradeoffs for solving directed graph connectivity or STCONN in small space. We use a strategy parameterized by a parameter k that uses k pebbles and...
Polynomials that Sign Represent Parity and Descartes Rule of Signs (2007)
Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton
We study the sparsity of real polynomials that sign represent parity on n variables, each of which takes values from some finite subset A of integers. While the degree of such polynomials has been...
Polynomials that Sign Represent Parity and Descartes' Rule of Signs (2007)
Basu, Saugata, Bhatnagar, Nayantara, Gopalan, Parikshit, Lipton, Richard J.
A real polynomial $P(X_1,..., X_n)$ sign represents $f: A^n \to \{0,1\}$ if for every $(a_1, ..., a_n) \in A^n$, the sign of $P(a_1,...,a_n)$ equals $(-1)^{f(a_1,...,a_n)}$. Such sign representations...
Algorithmic game theory (2007)
Richard J. Lipton, Vijay V. Vazirani, Milena Mihail, Craig Tovey, Eric Vigoda
I dedicate this thesis to my parents, Anjani and Sitanshu Mehta. iii ACKNOWLEDGEMENTS I would like to thank Dick Lipton and Vijay Vazirani, for their continuous support and guidance throughout these...
Some Remarks on the Jacobian Conjecture and Connections with Hilbert's Irreducibility Theorem (2005)
Lipton, Richard J., Markakis, Evangelos
We make two observations regarding the invertibility of Keller maps. i.e., polynomial maps for which the determinant of their Jacobian matrix is identically equal to 1. In our first result, we show...
Inapproximability results for combinatorial auctions with submodular utility functions (2005)
Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
We consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the...
Richard J. Lipton, Aranyak Mehta, Evangelos Markakis, Nisheeth K. Vishnoi
We study the following question: What is the smallest t such that every symmetric boolean function on k variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of...
Anne Condon, Richard J. Lipton
We prove two results on interactive proof systems with 2-way probabilistic finite state verifiers. The first is a lower bound on the power of such proof systems, if they are not required to halt with...
Inapproximability results for combinatorial auctions with submodular utility functions (2005)
Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
We consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the...
A Generalization of the Characteristic Polynomial of a Graph (2003)
Lipton, Richard J., Vishnoi, Nisheeth Kumar, Zalcstein, Yechezkel (Zeke)
Given a graph G with its adjacency matrix A, consider the matrix A(x, y) in which the 1s are replaced by the indeter0minate x and 0s (other than the diagonals) are replaced by y. The ℒ-polynomial...
A Local-global Principle for Diophantine Equations (2003)
Lipton, Richard J., Vishnoi, Nisheeth Kumar
We observe the following global-local principle for Diophantine equations: If an equation f(x₁,...,x[subscript t]) ϵ ℤ[x₁,...,x[subscript t] = p can be solved efficiently for a dense set of...
Improved Bounds for Learning Symmetric Juntas (2003)
Lipton, Richard J., Markakis, Evangelos
We consider a fundamental problem in computational learning theory: learning in the presence of irrelevant information. In particular we are interested in learning an arbitrary boolean function of n...
Symmetric polynomials over Zm and simultaneous communication protocols (2003)
Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton
We study the problem of representing symmetric Boolean functions as symmetric polynomials over Zm. We show an equivalence between such representations and simultaneous communication protocols....
Who's The Weakest Link? (2003)
Nikhil Devanur Richard, Richard J. Lipton, Nisheeth Vishnoi
In this paper we consider the following problem: Given a network G, determine if there is an edge in G through which at least c shortest paths pass. This problem arises naturally in various practical...
Playing Large Games using Simple Strategies (2003)
Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
We prove the existence of #-Nash equilibrium strategies with support logarithmic in the number of pure strategies. We also show that the payo#s to all players in any (exact) Nash equilibrium can be...
A Generalization of the Characteristic Polynomial of a Graph (2003)
Lipton, Richard J., Vishnoi, Nisheeth Kumar, Zalcstein, Yechezkel (Zeke)
Given a graph G with its adjacency matrix A, consider the matrix A(x, y) in which the 1s are replaced by the indeter0minate x and 0s (other than the diagonals) are replaced by y. The ℒ-polynomial...
A Local-global Principle for Diophantine Equations (2003)
Lipton, Richard J., Vishnoi, Nisheeth Kumar
We observe the following global-local principle for Diophantine equations: If an equation f(x₁,...,x[subscript t]) ϵ ℤ[x₁,...,x[subscript t] = p can be solved efficiently for a dense set of...
Improved Bounds for Learning Symmetric Juntas (2003)
Lipton, Richard J., Markakis, Evangelos
We consider a fundamental problem in computational learning theory: learning in the presence of irrelevant information. In particular we are interested in learning an arbitrary boolean function of n...
Gamma System: Continuous Evolution of Software after Deployment (2002)
Orso, Alessandro, Liang, Donglin, Harrold, Mary Jean, Lipton, Richard J.
In this paper, we present the Gamma system---a new approach for continuous improvement of software systems after their deployment. The Gamma system facilitates remote monitoring of deployed software...
In this work, we clarify, extend and solve an open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We first focus on the...
The Enforcement of Security Policies for Computation. (2002)
Jones,Anita K., Lipton,Richard J.
Security policies define how information within a computer system is to be used. Protection mechanisms are built into these systems to enforce security policies. However, in most systems it is quite...
Preserving Average Proximity in Arrays. (2002)
DeMillo,Richard A., Eisenstat,Stanley C., Lipton,Richard J.
The combinatorial problem of storage arrays as various kinds of list structures is examined. Embeddings of graphs are used to model the loss of proximity involved in such storage schemes, and an...
A Linear Time Algorithm for Deciding Security. (2002)
Jones,Anita K., Lipton,Richard J., Snyder,Lawrence
The take-grant security system is introduced. Active security agents (subjects) and passive entities (objects) are recognized. A linear time algorithm for recognizing security violations follows from...
A Probabilistic Remark on Algebraic Program Testing. (2002)
DeMillo,Richard A., Lipton,Richard J.
A key step in Howden's method for algebraic program testing requires checking the algebraic identity of multinomials. Howden's solution requires evaluations in at least 2 to the mth power points for...
The Average Length of Paths Embedded in Trees. (2002)
DeMillo,Richard A., Lipton,Richard J.
Let A sub n be defined so that the n x n array is embeddable in binary trees by dilating average path length by at most a factor of A sub n. It is shown that as n approaches infinity the limit of A...
Evaluation Criteria for Process Synchronization. (2002)
Lipton,Richard J., Snyder,Lawrence, Zalcstein,Y.
While there are by now well-established criteria for evaluating serial algorithms, such as space and time measures, these criteria cannot be readily applied to asynchronous algorithms. A method is...
The Complexity of Word and Isomorphism Problems for Finite Groups. (2002)
Lipton,Richard J., Snyder,Lawrence, Zalcstein,Y.
The uniform word problem for finite groups presented by their multiplication tables is considered. Upper bounds of 0(k-squared) for arbitrary group and 0(n log-squared n) for arbitrary semigroup and...
A Separator Theorem for Planar Graphs. (2002)
Lipton,Richard J., Tarjan,Robert E.
Let G be any n-vertex planar graph. Prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more...
Applications of a Planar Separator Theorem. (2002)
Lipton,Richard J., Tarjan,Robert E.
Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only O(square root of n) vertices. This separator theorem, in combination with a...
Even Data Bases That Lie Can be Compromised. (2002)
DeMillo,Richard A., Dobkin,David, Lipton,Richard J.
Users can compromise data bases by asking a series of questions, even when the data systems are allowed to lie. (Author)
On Small Universal Data Structures and Related Combinatorial Problems. (2002)
DeMillo,Richard A., Eisenstat,Stanley, Lipton,Richard J.
A universal graph for a class of graphs T is a graph G such that every graph in T can be embedded in G with worst-case (average case) loss of proximity bounded by a fixed constant. A universal graph...
Space-Time Tradeoffs in Structured Programming: An Improved Combinatorial Embedding Theorem. (2002)
DeMillo,Richard A., Eisenstat,Stanley C., Lipton,Richard J.
Let G and G* be programs represented by directed graphs. We define a relation < or = sub S, T between G and G* that formalizes the notion of G* simulating G with S-fold loss of space efficiency and...
Social Processes and Proofs of Theorems and Programs (Revised Version). (2002)
DeMillo,Richard A., Lipton,Richard J., Perlis,Alan J.
It has been extensively argued that the art and science of programming should strive to become more like mathematics. In this paper we argue that this point of view is correct, but that the reasons...
Budd,Timothy A., Lipton,Richard J., DeMillo,Richard A., Sayward,Frederick G.
A new type of software test is introduced, called mutation analysis. A method for applying mutation analysis is described, and the results of several experiments to determine its effectiveness are...
Introduction to Linear Asynchronous Structures, (2002)
Lipton,Richard J., Miller,Raymond E., Snyder,Lawrence
A bounded asynchronous model of computation is presented. Several of its basic properties are then obtained. (Author)
Synchronization and Computing Capabilities of Linear Asynchronous Structures. (2002)
Lipton,Richard J., Miller,Raymond E., Snyder,Lawrence
A model is defined in which questions concerning delay bounded asynchronous parallel systems may be investigated. It is shown that synchronization problems, similar to the firing squad...
On Structure Preserving Reductions. (2002)
Lipton,Richard J., Lynch,Nancy
The concept of reduction between problems is strengthened. Certain standard problems are shown to be complete in the new and stronger sense. Applications to the number of solutions of particular...
On the Complexity of Linear Search Tree Programs for Searching (Extended Abstract). (2002)
Lipton,Richard J., Dobkin,David
A set of general tools are obtained for proving nontrivial lower bounds on the class of linear search trees. Among them is an n squared lower bound on the classic knapsack problem. (Author)
DeMillo,Richard A., Lipton,Richard J.
A constructive adaptation of the Borel-Cantelli Lemma is obtained. Applications to several problems of complexity include the existence of hard 0,1 polynomials. (Author)
A Linear Time Algorithm for Deciding Subject Security. (2002)
Lipton,Richard J., Snyder,Lawrence
A particular protection mechanism from the protection literature -- the take and grant system -- is presented. For this particular mechanism it is shown that the safety problem can be solved in...
Linear Time Coloring of Planar Graphs. (2002)
Lipton,Richard J., Miller,Raymond E.
It is shown how to color a planar with 5-colors in linear time. The batching method used may have additional applications to other graph theory problems. (Author)
The Complexity of Searching Lines in the Plane: Preliminary Version. (2002)
Lipton,Richard J., Dobkin,David
Searching is a fundamental operation of computer science. Yet a number of key mathematical questions about searching in Euclidian spaces remains open. A number of such questions are formulated and...
On the Power of Applicative Languages. (2002)
Lipton,Richard J., Snyder,Lawrence
The expressive power of applicative structures is investigated (particularly APL one-liners) with the result that all practically computable functions are one-liner expressible. In particular, the...
On An Array Sorting Problem of Kosaraju. (2002)
Lipton,Richard J., Miller,Raymond E., Snyder,Lawrence
An array sorting problem is shown to have a linear lower time bound for n x n arrays. This negatively settles a conjecture of Kosaraju. Several other sorting schemes are considered, but all fail to...
Some Results on Maximum a Posteriori Probability Parsing Algorithms. (2002)
Lipton,Richard J., Snyder,Lawrence, Levinson,S. E.
A fast method of parsing noisy speech is sketched. It is then used to study the entropy of languages. (Author)
On the Halting of Tree Replacement Systems. (2002)
Lipton,Richard J., Snyder,Lawrence
A meta theorem is proved giving sufficient conditions for termination of tree replacement systems. This leads to a new proof methodology for proving termination of optimization techniques. (Author)
Increasing Confidence in Software through Program Perturbations. (2002)
Hanson,David, Lipton,Richard J., Sayward,Frederick G.
A new method for increasing confidence in software based on the premise that competent programmers write correct or 'nearly' correct software is presented. The envisioned system takes as input a...
Some Connection Between Mathematical Logic and Complexity Theory, (2002)
DeMillo,Richard A., Lipton,Richard J.
The existence of lower bounds for problems in NP intersection coNP is equivalent to the existence of nonstandard, noneffective models of a fragment, PT, of complete arthmetic. A typical corrollary is...
Acree ,Allen T., Budd ,Timothy A., DeMillo ,Richard A., Lipton ,Richard J., Sayward,Frederick G.
A new Type of software test, called mutation analysis, is introduced. A method of applying mutation analysis is described, and the design of several existing automated systems for applying mutation...
Budd,Timothy A., DeMillo,Richard A., Lipton,Richard J., Sayward,Frederick G.
A framework for studying the program mutation testing method from both theoretical and empirical viewpoints is presented. (Author)
A System Architecture to Support a Verifiably Secure Multilevel Security System. (2002)
Davida,George I., DeMilo,Richard A., Lipton,Richard J.
Technology that allows significant sharing of computer resources carriers with it an increased responsibility to protect these resources from unauthorized, malicious, irresponsible, or unintended use...
Software Project Forecasting, (2002)
DeMillo,Richard A., Lipton,Richard J.
We have argued that a major use of software metrics is in the forecasting problem for software projects. By analogy with weather forecasting, we may characterize the current state of knowledge in...
Sayward,Frederick G., Lipton,Richard J.
Program mutation is a promising method for testing the functional correctness of programs. Its major criticism has been a lack of an efficient implementation method. This report presents four methods...
Papers on Program Testing, (2002)
DeMillo, Richard A., Lipton, Richard J., Sayward, Frederick G.
Since late 1976, we have been involved in what we believe is a new approach to computer program testing, an approach called mutation analysis (and we shall forever be indebted to Jerome Feldman for...
Abstract Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory (2002)
Richard J. Lipton, Neal E. Young
Von Neumann’s Min-Max Theorem guarantees that each player of a zero-sum matrix game has an optimal mixed strategy. We show that each player has a near-optimal mixed strategy that chooses uniformly...
concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We rst focus on the dierence between the time a packet nishes service in a...
Gamma System: Continuous Evolution of Software after Deployment (2002)
Orso, Alessandro, Liang, Donglin, Harrold, Mary Jean, Lipton, Richard J.
In this paper, we present the Gamma system---a new approach for continuous improvement of software systems after their deployment. The Gamma system facilitates remote monitoring of deployed software...
In this work, we clarify, extend and solve an open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We first focus on the...
Mandatory Human Participation: A New Scheme for Building Secure Systems (2001)
Xu, Jun, Essa, Irfan A., Sung, Min-Ho, Lipton, Richard J.
Mandatory Human Participation (MHP) is a novel authentication scheme that asks the question "are you human?" (instead of "who are you?"), and upon the correct answer to this question, can prove a...
On the Importance of Eliminating Errors in Cryptographic Computations (2001)
Dan Boneh, Richard A. Demillo, Richard J. Lipton
We present a model for attacking various cryptographic schemes by taking advantage of random hardware faults. The model consists of a black-box containing some cryptographic secret. The box interacts...
Mandatory Human Participation: A New Scheme for Building Secure Systems (2001)
Xu, Jun, Essa, Irfan A., Sung, Min-Ho, Lipton, Richard J.
Mandatory Human Participation (MHP) is a novel authentication scheme that asks the question "are you human?" (instead of "who are you?"), and upon the correct answer to this question, can prove a...
Xu, Jun, Essa, Irfan A., Lipton, Richard J.
In this paper, we propose the concept of a humanizer and explore its applications in network security and E-commerce. A humanizer is a novel authentication scheme that asks the question "are you...
On the Complexity of Intersecting Finite State Automata (2000)
George Karakostas, Richard J. Lipton, Anastasios Viglas
We consider the problem of testing whether the intersection of a collection of k automata is empty. The straightforward algorithm for solving this problem runs in time # k where # is the size of the...
Xu, Jun, Essa, Irfan A., Lipton, Richard J.
In this paper, we propose the concept of a humanizer and explore its applications in network security and E-commerce. A humanizer is a novel authentication scheme that asks the question "are you...
Computing from partial solutions (1999)
Shai Halevi, Richard J. Lipton, Erez Petrank
We consider the question: Is finding just a part of a solution easier than finding the full solution? For example, is finding only an ffl fraction of the bits in a satisfying assignment to a 3-CNF...
Computing From Partial Solutions (1999)
Anna Al Shai, Shai Halevi, Richard J. Lipton, Erez Petrank
We consider the question: Is finding just a part of a solution easier than finding the full solution? For example, is finding only an ffl fraction of the bits in a satisfying assignment to a 3-CNF...
On the Power of Automata Based Proof Systems (1999)
Richard J. Lipton, Anastasios Viglas
One way to address the NP = co - NP question is to consider the length of proofs of tautologies in various proof systems. In this work we consider proof systems defined by appropriate classes of...
On the Complexity of SAT (1999)
Richard J. Lipton, Anastasios Viglas
We show that non-deterministic time NT IME(n) is not contained in deterministic time n 2-# and poly-logarithmic space, for any # > 0. This implies that (infinitely often) satisfiability cannot be...
Reconstructing Algebraic Functions from Mixed Data (1998)
Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan
.<F3.822e+05> We consider a variant of the traditional task of explicitly reconstructing algebraic functions from black box representations. In the traditional setting for such problems, one is...
On the Importance of Checking Cryptographic Protocols for Faults (1997)
Dan Boneh, Richard A. Demillo, Richard J. Lipton
We present a theoretical model for breaking various cryptographic schemes by taking advantage of random hardware faults. We show how to attack certain implementations of RSA and Rabin signatures. An...
Reconstructing Algebraic Functions from Mixed Data (1997)
Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan
We consider a variant of the traditional task of explicitly reconstructing algebraic functions from black box representations. In the traditional setting for such problems, one is given access to an...
On the computational power of dna (1996)
Dan Boneh, Christopher Dunworth, Jill Sgallt, Richard J. Lipton
We show how DNA based computers can be used to solve the satisfiability problem for boolean circuits. Furthermore, we show how DNA computers can solve optimization problems directly without first...
Dan Boneh, Richard A. Demillo, Richard J. Lipton
We present a theoretical model for breaking various cryptographic schemes by taking advantage of random hardware faults. We show how to attack certain implementations of RSA and Rabin signatures. We...
On the Importance of Checking Computations (Extended abstract) (1996)
Dan Boneh, Richard A. Demillo, Richard J. Lipton
We present a theoretical model for breaking various cryptographic schemes by taking advantage of random hardware faults. We show how to attack certain implementations of RSA and Rabin signatures. We...
Breaking DES Using a Molecular Computer (1995)
Dan Boneh, Christopher Dunworth, Richard J. Lipton
Recently Adleman [1] has shown that a small traveling salesman problem can be solved by molecular operations. In this paper we show how the same principles can be applied to breaking the Data...
Making DNA computers error resistant (1995)
Dan Boneh, Christopher Dunworth, Richard J. Lipton
We describe methods for making volume decreasing algorithms more resistant to certain types of errors. Such error recovery techniques are crucial if DNA computers ever become practical. Our first...
Making DNA Computers Error Resistant (1995)
this paper. All DNA algorithms use strands of DNA to encode many parallel computations. They naturally fall into three classes: Algorithms are Decreasing Volume if the number of strands decreases as...
On The Computational Power of DNA (1995)
Dan Boneh, Christopher Dunworth, Richard J. Lipton, Jiri Sgall
We show how DNA based computers can be used to solve the satisfiability problem for boolean circuits. Furthermore, we show how DNA computers can solve optimization problems directly without first...
Making DNA Computers Error Resistant (1995)
Dan Boneh, Christopher Dunworth, Richard J. Lipton, Jiri Sgall
We describe methods for making volume decreasing algorithms more resistant to certain types of errors. Such error recovery techniques are crucial if DNA computers ever become practical. Our first...
Simple strategies for large zero-sum games with applications to complexity theory (1994)
Richard J. Lipton, Neal E. Young
Von Neumann's Min-Max Theorem guarantees that each player of a zero-sum matrix game has an optimal mixed strategy. We show that each player has a near-optimal mixed strategy that chooses...
Communication Complexity of Key Agreement on Limited Ranges (Extended Abstract) (1994)
Jin-yi Cai, Richard J. Lipton, Luc Longpré, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar
This paper studies a variation on classical key-agreement and consensus problems in which the set S of possible keys is the range of a random variable that can be sampled. We give tight upper and...
Cryptographic Primitives Based on Hard Learning Problems (1994)
Avrim Blum, Merrick Furst, Michael Kearns, Richard J. Lipton
this paper, we give results in the reverse direction by showing how to construct several cryptographic primitives based on certain assumptions on the difficulty of learning. In doing so, we develop...
Online Interval Scheduling (1994)
Richard J. Lipton, Andrew Tomkins
We introduce the online interval scheduling problem, in which a set of intervals of the positive real line is presented to a scheduling algorithm in order of start time. Upon seeing each interval,...
Speeding Up Computations via Molecular Biology (1994)
: We show how to extend the recent result of Adleman [1] to use biological experiments to directly solve any NP problem. We, then, show how to use this method to speedup a large class of important...
Communication Complexity of Key Agreement on Small Ranges (Preliminary Version) (1994)
Jin-yi Cai, Richard J. Lipton, Luc Longpré, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar
This paper studies a variation on classical key-agreement and consensus problems in which the set S of possible keys is the range of a random variable that can be sampled. We give tight upper and...
Reconstructing algebraic functions from mixed data (1992)
Richard J. Lipton, Ronitt Rubinfeld
Abstract. We consider a variant of the traditional task of explicitly reconstructing algebraic functions from black box representations. In the traditional setting for such problems, one is given...
Reconstructing algebraic functions from mixed data (1992)
Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld
We consider the task of reconstructing algebraic functions given by black boxes. Unlike traditional settings, we are interested in black boxes which represent several algebraic functions- f 1; : : :...
Reconstructing algebraic functions from mixed data (1992)
Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld
We consider a variant of the traditional task of explicitly reconstructing algebraic functions from black box representations. In the traditional setting for such problems, one is given access to an...
PSPACE Is Provable By Two Provers In One Round (1991)
Jin-Yi Cai, Richard J. Lipton, Anne Condon, Anne Condon
We show that every language in PSPACE, or equivalently every language accepted by an unbounded round interactive proof system, has a 1-round, 2-prover interactive proof system with exponentially...
Richard J. Lipton, David W. Mizell, Richard J. Lipton, David W. Mizell, Richard J. Lipton
the proceedings of the SCS Multiconference
Practical Selectivity Estimation through Adaptive Sampling (1990)
Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider
Recently we have proposed an adaptive, random sampling algorithm for general query size estimation. In earlier work we analyzed the asymptotic efficiency and accuracy of the algorithm; in this paper...
Beyer, Robert E., Starnes, Joseph W., Edington, Dee W., Lipton, Richard J., Kwasman, Michael A.
The ability of gastrocnemius muscle homogenates to catalyze the oxidation of succinate, glutamate + malate, pyruvate + malate, palmitoyl-coenzyme A, decanoylcarnitine and palmitoylcarnitine in the...
Ashok K. Chandra, I Merrick, L. Furst, Richard J. Lipton
process communication have been examined from a complexity pbint of view [SP, Y]. We study a new model, in which a collection of processes eo, "'', e~:~l
Secure databases: Protection against user influence (1979)
David Dobkin, Anita K. Jones, Richard J. Lipton
Users may be able to compromise databases by asking a series of questions and then inferring new information from the answers. The complexity of protecting a database against this technique is...
Abstract. A Separator Theorem for Planar Graphs f * (1977)
Richard J. Lipton, Robert E. Tarjan, Richard J. Lipton, Robert Andre Tarjan
Let G be any n-vertex planar graph. We prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more...
On synchronization primitive systems /--by Richard J. Lipton. (1973)
"This work was supported by the Advanced Research Projects Agency of the Office of the Secretary of Defense ... and is monitored by the Air Force Office of Scientific Research."
Molecular computation: RNA solutions to chess problems
Faulhammer, Dirk, Cukras, Anthony R., Lipton, Richard J., Landweber, Laura F.
We have expanded the field of “DNA computers” to RNA and present a general approach for the solution of satisfiability problems. As an example, we consider a variant of the “Knight problem,”...
Molecular computation: RNA solutions to chess problems
Faulhammer, Dirk, Cukras, Anthony R., Lipton, Richard J., Landweber, Laura F.
We have expanded the field of “DNA computers” to RNA and present a general approach for the solution of satisfiability problems. As an example, we consider a variant of the “Knight problem,”...
On the Computational Power of DNA
Dan Boneh, Christopher Dunworth, Richard J. Lipton, Jiri Sgall
We show how DNA based computers can be used to solve the satisfiability problem for boolean circuits. Furthermore, we show how DNA computers can solve optimization problems directly without first...
On The Computational Power of DNA
Dan Boneh, Christopher Dunworth, Richard J. Lipton
We show how DNA based computers can be used to solve the satisfiability problem for boolean circuits. Furthermore, we show how DNA computers can solve optimization problems directly without first...