Richard J. Lipton

According to our database, Richard J. Lipton authored at least 199 papers between 1974 and 2022.

Collaborative distances:

• Dijkstra number of one.
• Erdős number of two.

2022

On the Skolem Problem and the Skolem Conjecture.

Richard Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser, James Worrell

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

2020

On the skolem problem and prime powers.

George Kenison, Richard Lipton, Joël Ouaknine, James Worrell

Proceedings of the ISSAC '20: International Symposium on Symbolic and Algebraic Computation, 2020

2016

Provably-Secure Remote Memory Attestation for Heap Overflow Protection.

Alexandra Boldyreva, Taesoo Kim, Richard J. Lipton, Bogdan Warinschi

Proceedings of the Security and Cryptography for Networks - 10th International Conference, 2016

Provably Secure Virus Detection: Using The Observer Effect Against Malware.

Richard J. Lipton, Rafail Ostrovsky, Vassilis Zikas

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Provable Virus Detection: Using the Uncertainty Principle to Protect Against Malware.

Richard J. Lipton, Rafail Ostrovsky, Vassilis Zikas

IACR Cryptol. ePrint Arch., 2015

Towards Provably-Secure Remote Memory Attestation.

Alexandra Boldyreva, Taesoo Kim, Richard J. Lipton, Bogdan Warinschi

IACR Cryptol. ePrint Arch., 2015

2013

An Approximate Restatement of the Four-Color Theorem.

Atish Das Sarma, Amita Gajewar, Richard J. Lipton, Danupon Nanongkai

J. Graph Algorithms Appl., 2013

Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs.

Parinya Chalermsook, Shiva Kintali, Richard J. Lipton, Danupon Nanongkai

Chic. J. Theor. Comput. Sci., 2013

Amplifying circuit lower bounds against polynomial time, with applications.

Richard J. Lipton, Ryan Williams

Comput. Complex., 2013

People, Problems, and Proofs - Essays from Gödel's Lost Letter: 2010.

Richard J. Lipton, Kenneth W. Regan

Springer, ISBN: 978-3-642-41421-3, 2013

2012

Improved simulation of nondeterministic Turing machines.

Subrahmanyam Kalyanasundaram, Richard J. Lipton, Kenneth W. Regan, Farbod Shokrieh

Theor. Comput. Sci., 2012

Simulating Special but Natural Quantum Circuits

Richard J. Lipton, Kenneth W. Regan, Atri Rudra

CoRR, 2012

Might Turing Have Won a Turing Award?

Richard J. Lipton

Computer, 2012

2011

Best-order streaming model.

Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai

Theor. Comput. Sci., 2011

Quantum Complexity: Some Recent Results, Some Open Problems, Some Thoughts.

Richard J. Lipton

Proceedings of the Theory and Applications of Models of Computation, 2011

Symmetric Functions Capture General Functions.

Richard J. Lipton, Kenneth W. Regan, Atri Rudra

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Representative skylines using threshold-based preference distributions.

Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Richard J. Lipton, Jun (Jim) Xu

Proceedings of the 27th International Conference on Data Engineering, 2011

2010

Regret-Minimizing Representative Databases.

Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Richard J. Lipton, Jun (Jim) Xu

Proc. VLDB Endow., 2010

On Tractable Exponential Sums.

Jin-yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu

Proceedings of the Frontiers in Algorithmics, 4th International Workshop, 2010

Platform-independent programs.

Sang Kil Cha, Brian Pak, David Brumley, Richard Jay Lipton

Proceedings of the 17th ACM Conference on Computer and Communications Security, 2010

2009

Deterministically testing sparse polynomial identities of unbounded degree.

Markus Bläser, Moritz Hardt, Richard J. Lipton, Nisheeth K. Vishnoi

Inf. Process. Lett., 2009

On the Fourier spectrum of symmetric Boolean functions.

Mihail N. Kolountzakis, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi

Comb., 2009

Social Network Privacy via Evolving Access Control.

Giovanni Di Crescenzo, Richard J. Lipton

Proceedings of the Wireless Algorithms, 2009

Algorithms for Message Ferrying on Mobile ad hoc Networks.

Mostafa H. Ammar, Deeparnab Chakrabarty, Atish Das Sarma, Subrahmanyam Kalyanasundaram, Richard J. Lipton

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

2008

Polynomials that Sign Represent Parity and Descartes' Rule of Signs.

Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Comput. Complex., 2008

Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions.

Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta

Algorithmica, 2008

Algorithms for Modular Counting of Roots of Multivariate Polynomials.

Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton

Algorithmica, 2008

2007

Intrusion-Resilient Key Exchange in the Bounded Retrieval Model.

David Cash, Yan Zong Ding, Yevgeniy Dodis, Wenke Lee, Richard J. Lipton, Shabsi Walfish

Proceedings of the Theory of Cryptography, 4th Theory of Cryptography Conference, 2007

2006

Symmetric polynomials over Z_<i>m</i> and simultaneous communication protocols.

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

J. Comput. Syst. Sci., 2006

Perfectly Secure Password Protocols in the Bounded Retrieval Model.

Giovanni Di Crescenzo, Richard J. Lipton, Shabsi Walfish

Proceedings of the Theory of Cryptography, Third Theory of Cryptography Conference, 2006

Towards the integration of diverse spam filtering techniques.

Calton Pu, Steve Webb, Oleg M. Kolesnikov, Wenke Lee, Richard J. Lipton

Proceedings of the 2006 IEEE International Conference on Granular Computing, 2006

2005

On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms.

Jun (Jim) Xu, Richard J. Lipton

IEEE/ACM Trans. Netw., 2005

Estimating the maximum.

Ben Gum, Richard J. Lipton, Andrea S. LaPaugh, Faith E. Fich

J. Algorithms, 2005

Time-space lower bounds for satisfiability.

Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas

J. ACM, 2005

Protecting Secret Data from Insider Attacks.

David Dagon, Wenke Lee, Richard J. Lipton

Proceedings of the Financial Cryptography and Data Security, 2005

On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas.

Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

The Degree of Threshold Mod 6 and Diophantine Equations

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Electron. Colloquium Comput. Complex., 2004

On approximately fair allocations of indivisible goods.

Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, Amin Saberi

Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004

Nash Equilibria via Polynomial Equations.

Richard J. Lipton, Evangelos Markakis

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

On the Complexity of Hilbert's 17th Problem.

Nikhil R. Devanur, Richard J. Lipton, Nisheeth K. Vishnoi

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

2003

On the complexity of intersecting finite state automata and N L versus N P.

George Karakostas, Richard J. Lipton, Anastasios Viglas

Theor. Comput. Sci., 2003

A Note on Square Rooting of Time Functions of Turing Machines.

Richard J. Lipton, Mitsunori Ogihara, Yechezkel Zalcstein

Theory Comput. Syst., 2003

Symmetric Polynomials over Z_m and Simultaneous Communication Protocols

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Electron. Colloquium Comput. Complex., 2003

Deterministic identity testing for multivariate polynomials.

Richard J. Lipton, Nisheeth K. Vishnoi

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Playing large games using simple strategies.

Richard J. Lipton, Evangelos Markakis, Aranyak Mehta

Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

Who's The Weakest Link?

Nikhil R. Devanur, Richard J. Lipton, Nisheeth K. Vishnoi

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2003

Mandatory human participation: a new authentication scheme for building secure systems.

Jun Xu, Richard J. Lipton, Irfan A. Essa, Minho Sung, Yong Zhu

Proceedings of the 12th International Conference on Computer Communications and Networks, 2003

Randomized Time-Space Tradeoffs for Directed Graph Connectivity.

Parikshit Gopalan, Richard J. Lipton, Aranyak Mehta

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

Symmetric Polynomials over Z_m and Simultaneous Communication Protocol.

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

Network and service security.

Richard J. Lipton, S. Raj Rajagopalan, Dimitrios Serpanos

IEEE Netw., 2002

Non-uniform Depth of Polynomial Time and Space Simulations

Richard J. Lipton, Anastasios Viglas

Electron. Colloquium Comput. Complex., 2002

Gamma system: continuous evolution of software after deployment.

Alessandro Orso, Donglin Liang, Mary Jean Harrold, Richard J. Lipton

Proceedings of the International Symposium on Software Testing and Analysis, 2002

Spy: A Method to Secure Clients for Network Services.

Richard J. Lipton, S. Raj Rajagopalan, Dimitrios N. Serpanos

Proceedings of the 22nd International Conference on Distributed Computing Systems, 2002

2001

On the Importance of Eliminating Errors in Cryptographic Computations.

Dan Boneh, Richard A. DeMillo, Richard J. Lipton

J. Cryptol., 2001

Cheaper by the Dozen: Batched Algorithms.

Ben Gum, Richard J. Lipton

Proceedings of the First SIAM International Conference on Data Mining, 2001

Defense Against Man-in-the-Middle Attack in Client-Server Systems.

Dimitrios N. Serpanos, Richard J. Lipton

Proceedings of the Sixth IEEE Symposium on Computers and Communications (ISCC 2001), 2001

2000

The Complexity of the A B C Problem.

Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein

SIAM J. Comput., 2000

Molecular computation: RNA solutions to chess problems.

Dirk Faulhammer, Anthony R. Cukras, Richard J. Lipton, Laura F. Landweber

Proc. Natl. Acad. Sci. USA, 2000

Fidelity of Enzymatic Ligation for DNA Computing.

Dirk Faulhammer, Richard J. Lipton, Laura F. Landweber

J. Comput. Biol., 2000

On the Complexity of Intersecting Finite State Automata.

George Karakostas, Richard J. Lipton, Anastasios Viglas

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

On the Complexity of SAT.

Richard J. Lipton, Anastasios Viglas

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

When the Knight falls: On constructing an RNA computer.

Dirk Faulhammer, Anthony R. Cukras, Richard J. Lipton, Laura F. Landweber

Proceedings of the DNA Based Computers, 1999

Computing from Partial Solutions.

Anna Gál, Shai Halevi, Richard J. Lipton, Erez Petrank

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

Reconstructing Algebraic Functions from Mixed Data.

Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan

SIAM J. Comput., 1998

Micropayments via Efficient Coin-Flipping.

Richard J. Lipton, Rafail Ostrovsky

Proceedings of the Financial Cryptography, 1998

1997

DNA²DNA Computation: A Potential Killer Application?

Richard J. Lipton

Proceedings of the Advances in Neural Information Processing Systems 10, 1997

Effect of Operators on Straight Line Complexity.

Dan Boneh, Richard J. Lipton

Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

DNA²DNA Computations: A Potential "Killer App"?

Laura F. Landweber, Richard J. Lipton

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

On the Complexity of a Set-Union Problem.

Richard J. Lipton, Paul J. Martino, Andy Neitzke

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

On the Importance of Checking Cryptographic Protocols for Faults (Extended Abstract).

Dan Boneh, Richard A. DeMillo, Richard J. Lipton

Proceedings of the Advances in Cryptology, 1997

DNA²DNA computations: A potential "killer app?".

Laura F. Landweber, Richard J. Lipton, Michael O. Rabin

Proceedings of the DNA Based Computers, 1997

1996

The Expressive Power of Multi-parent Creation in Monotonic Access Control Models.

Paul Ammann, Richard J. Lipton, Ravi S. Sandhu

J. Comput. Secur., 1996

On Proving that a Graph has no Large Clique: A Connection with Ramsey Theory.

Richard J. Lipton

Inf. Process. Lett., 1996

On the Computational Power of DNA.

Dan Boneh, Christopher Dunworth, Richard J. Lipton, Jirí Sgall

Discret. Appl. Math., 1996

A Revocable Backup System.

Dan Boneh, Richard J. Lipton

Proceedings of the 6th USENIX Security Symposium, San Jose, CA, USA, July 22-25, 1996, 1996

Clock Buffer Placement Algorithm for Wire-Delay-Dominated Timing Model.

Masato Edahiro, Richard J. Lipton

Proceedings of the 6th Great Lakes Symposium on VLSI (GLS-VLSI '96), 1996

DNA computations can have global memory.

Richard J. Lipton

Proceedings of the DNA Based Computers, 1996

Making DNA computers error resistant.

Dan Boneh, Christopher Dunworth, Richard J. Lipton, Jirí Sgall

Proceedings of the DNA Based Computers, 1996

Algorithms for Black-Box Fields and their Application to Cryptography (Extended Abstract).

Dan Boneh, Richard J. Lipton

Proceedings of the Advances in Cryptology, 1996

1995

Query Size Estimation by Adaptive Sampling.

Richard J. Lipton, Jeffrey F. Naughton

J. Comput. Syst. Sci., 1995

Communication Complexity of Key Agreement on Small Ranges.

Jin-yi Cai, Richard J. Lipton, Luc Longpré, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar

Proceedings of the STACS 95, 1995

Speeding up computations via molecular biology.

Richard J. Lipton

Proceedings of the DNA Based Computers, 1995

Breaking DES using a molecular computer.

Dan Boneh, Christopher Dunworth, Richard J. Lipton

Proceedings of the DNA Based Computers, 1995

Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract).

Dan Boneh, Richard J. Lipton

Proceedings of the Advances in Cryptology, 1995

1994

Subquadratic Simulations of Balanced Formulae by Branching Programs.

Jin-yi Cai, Richard J. Lipton

SIAM J. Comput., 1994

PSPACE Is Provable by Two Provers in One Round.

Jin-yi Cai, Anne Condon, Richard J. Lipton

J. Comput. Syst. Sci., 1994

Simple strategies for large zero-sum games with applications to complexity theory.

Richard J. Lipton, Neal E. Young

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

A New Approach To Information Theory.

Richard J. Lipton

Proceedings of the STACS 94, 1994

Online Interval Scheduling.

Richard J. Lipton, Andrew Tomkins

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices

Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Some Consequences of Our Failure to Prove Non-Linear Lower Bounds on Explicit Functions.

Richard J. Lipton

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

Straight-line complexity and integer factorization.

Richard J. Lipton

Proceedings of the Algorithmic Number Theory, First International Symposium, 1994

1993

Efficient Sampling Strategies for Relational Database Operations.

Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri

Theor. Comput. Sci., 1993

A Monte-Carlo Algorithm for Estimating the Permanent.

Narendra Karmarkar, Richard M. Karp, Richard J. Lipton, László Lovász, Michael Luby

SIAM J. Comput., 1993

Clocked Adversaries for Hashing.

Richard J. Lipton, Jeffrey F. Naughton

Algorithmica, 1993

Cryptographic Primitives Based on Hard Learning Problems.

Avrim Blum, Merrick L. Furst, Michael J. Kearns, Richard J. Lipton

Proceedings of the Advances in Cryptology, 1993

Amplification of Weak Learning under the Uniform Distribution.

Dan Boneh, Richard J. Lipton

Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

Towards Uncheatable benchmarks.

Jin-yi Cai, Richard J. Lipton, Robert Sedgewick, Andrew Chi-Chih Yao

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

On Games of Incomplete Information.

Jin-yi Cai, Anne Condon, Richard J. Lipton

Theor. Comput. Sci., 1992

How to Store a Triangular Matrix.

Andrea S. LaPaugh, Richard J. Lipton, Jonathan S. Sandberg

IEEE Trans. Computers, 1992

Probabilistic Dignosis of Hot Spots.

Kenneth Salem, Daniel Barbará, Richard J. Lipton

Proceedings of the Eighth International Conference on Data Engineering, 1992

The Expressive Power of Multi-Parent Creation in a Monotonic Access Control Model.

Paul Ammann, Richard J. Lipton, Ravi S. Sandhu

Proceedings of the 5th IEEE Computer Security Foundations Workshop, 1992

1991

Defining Software by Continuous, Smooth Functions.

Richard A. DeMillo, Richard J. Lipton

IEEE Trans. Software Eng., 1991

A Class of Randomized Strategies for Low-Cost Comparison of File Copies.

Daniel Barbará, Richard J. Lipton

IEEE Trans. Parallel Distributed Syst., 1991

Set systems with no union of cardinality 0 modulo<i>m</i>.

Noga Alon, Daniel J. Kleitman, Richard J. Lipton, Roy Meshulam, Michael O. Rabin, Joel H. Spencer

Graphs Comb., 1991

Self-Testing/Correcting for Polynomials and for Approximate Functions

Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

1990

IOStone: a synthetic file system benchmark.

Arvin Park, Jeffrey C. Becker, Richard J. Lipton

SIGARCH Comput. Archit. News, 1990

The Processor Identity Problem.

Richard J. Lipton, Arvin Park

Inf. Process. Lett., 1990

Efficient Checking of Computations.

Richard J. Lipton

Proceedings of the STACS 90, 1990

Playing Games of Incomplete Information.

Jin-yi Cai, Anne Condon, Richard J. Lipton

Proceedings of the STACS 90, 1990

Practical Selectivity Estimation through Adaptive Sampling.

Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider

Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, 1990

Uniform-Cost Communication in Scalable Multiprocessors.

Richard J. Lipton, Dimitrios N. Serpanos

Proceedings of the 1990 International Conference on Parallel Processing, 1990

On Bounded Round Multi-Prover Interactive Proof Systems.

Jin-yi Cai, Anne Condon, Richard J. Lipton

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

Array Access Bounds for Block Storage Memory Systems.

Arvin Park, Krishnaswamy Balasubramanian, Richard J. Lipton

IEEE Trans. Computers, 1989

Estimating the Size of Generalized Transitive Closures.

Richard J. Lipton, Jeffrey F. Naughton

Proceedings of the Fifteenth International Conference on Very Large Data Bases, 1989

A Randomized Technique for Remote File Comparison.

Daniel Barbará, Richard J. Lipton

Proceedings of the 9th International Conference on Distributed Computing Systems, 1989

On the Complexity of Space Bounded Interactive Proofs (Extended Abstract)

Anne Condon, Richard J. Lipton

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Subquadratic Simulations of Circuits by Branching Programs

Jin-yi Cai, Richard J. Lipton

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

New Directions In Testing.

Richard J. Lipton

Proceedings of the Distributed Computing And Cryptography, 1989

1986

Polynomial-time algorithm for the orbit problem.

Ravindran Kannan, Richard J. Lipton

J. ACM, 1986

Delta Transformations to Simplify VLSI Processor Arrays for Serial Dynamic Programming.

Richard J. Lipton, Daniel P. Lopresti

Proceedings of the International Conference on Parallel Processing, 1986

1985

Unbounded Fan-In Circuits and Associative Functions.

Ashok K. Chandra, Steven Fortune, Richard J. Lipton

J. Comput. Syst. Sci., 1985

Pseudorandom Number Generation and Space Complexity

Merrick L. Furst, Richard J. Lipton, Larry J. Stockmeyer

Inf. Control., 1985

The Role Of Massive Memory In Knowledge-Base Management Systems.

Richard E. Cullingford, Hector Garcia-Molina, Richard J. Lipton

Proceedings of the On Knowledge Base Management Systems: Integrating Artificial Intelligence and Database Technologies, 1985

A method for drawing graphs.

Richard J. Lipton, Stephen C. North, Jonathan S. Sandberg

Proceedings of the First Annual Symposium on Computational Geometry, 1985

1984

A Massive Memory Machine.

Hector Garcia-Molina, Richard J. Lipton, Jacobo Valdes

IEEE Trans. Computers, 1984

Alternating Pushdown and Stack Automata.

Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer

SIAM J. Comput., 1984

Alternation Bounded Auxiliary Pushdown Automata

Richard E. Ladner, Larry J. Stockmeyer, Richard J. Lipton

Inf. Control., 1984

1983

VLSI Layout as Programming.

Richard J. Lipton, Jacobo Valdes, Gopalakrishnan Vijayan, Stephen C. North, Robert Sedgewick

ACM Trans. Program. Lang. Syst., 1983

Multi-Party Protocols

Ashok K. Chandra, Merrick L. Furst, Richard J. Lipton

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Total Fault Testing Using the Bipartite Transformation.

Andrea S. LaPaugh, Richard J. Lipton

Proceedings of the Proceedings International Test Conference 1983, 1983

Lower Bounds for Constant Depth Circuits for Prefix Problems.

Ashok K. Chandra, Steven Fortune, Richard J. Lipton

Proceedings of the Automata, 1983

Total stuct-at-fault testing by circuit transformation.

Andrea S. LaPaugh, Richard J. Lipton

Proceedings of the 20th Design Automation Conference, 1983

1982

Programming Aspects of VLSI.

Richard J. Lipton, Robert Sedgewick, Jacobo Valdes

Proceedings of the Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages, 1982

ALI: A procedural language to describe VLSI layouts.

Richard J. Lipton, Stephen C. North, Robert Sedgewick, Jacobo Valdes, Gopalakrishnan Vijayan

Proceedings of the 19th Design Automation Conference, 1982

Design automation algorithms: Research and applications.

Richard J. Lipton, J. Daniel Nash

Proceedings of the 19th Design Automation Conference, 1982

1981

On the Structure of Sets in NP and Other Complexity Classes.

Lawrence H. Landweber, Richard J. Lipton, Edward L. Robertson

Theor. Comput. Sci., 1981

Covering Graphs by Simple Circuits.

Alon Itai, Richard J. Lipton, Christos H. Papadimitriou, Michael Rodeh

SIAM J. Comput., 1981

Computing Extremal and Approximate Distances in Graphs Having Unit Cost Edges.

Kellogg S. Booth, Richard J. Lipton

Acta Informatica, 1981

Lower Bounds for VLSI

Richard J. Lipton, Robert Sedgewick

Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

Multilevel Secure Distributed System.

George I. Davida, Richard A. DeMillo, Richard J. Lipton

Proceedings of the 2nd International Conference on Distributed Computing Systems, 1981

Census Functions: an Approach to VLSI Upper Bounds (Preliminary Version)

Richard J. Lipton, Jacobo Valdes

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980

Applications of a Planar Separator Theorem.

Richard J. Lipton, Robert Endre Tarjan

SIAM J. Comput., 1980

Addition Chain Methods for the Evaluation of Specific Polynomials.

David P. Dobkin, Richard J. Lipton

SIAM J. Comput., 1980

External Hashing Schemes for Collections of Data Structures.

Richard J. Lipton, Arnold L. Rosenberg, Andrew Chi-Chih Yao

J. ACM, 1980

Space-Time Trade-Offs in Structured Programming: An Improved Combinatorial Embedding Theorem.

Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton

J. ACM, 1980

Some Connections between Nonuniform and Uniform Complexity Classes

Richard M. Karp, Richard J. Lipton

Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

The Orbit Problem is Decidable

Ravindran Kannan, Richard J. Lipton

Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

The Consistency of "P = NP" and Related Problems with Fragments of Number Theory.

Richard A. DeMillo, Richard J. Lipton

Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

A System Architecture to Support a Verifiably Secure Multilevel Security System.

George I. Davida, Richard A. DeMillo, Richard J. Lipton

Proceedings of the 1980 IEEE Symposium on Security and Privacy, 1980

Protecting Shared Cryptographic Keys.

George I. Davida, Richard A. DeMillo, Richard J. Lipton

Proceedings of the 1980 IEEE Symposium on Security and Privacy, 1980

Theoretical and Emperical Studies on Using Program Mutation to Test the Functional Correctness of Programs.

Timothy A. Budd, Richard A. DeMillo, Richard J. Lipton, Frederick G. Sayward

Proceedings of the Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, 1980

1979

Secure Databases: Protection Against User Influence.

David P. Dobkin, Anita K. Jones, Richard J. Lipton

ACM Trans. Database Syst., 1979

Review of "Proofs and refutations: the logic of mathematical discovery" by Imre Lakatos. Cambridge University Press 1976.

Richard A. DeMillo, Richard J. Lipton

SIGACT News, 1979

A Constructive Generalization of the Borel-Cantelli Lemma with Application to the Complexity of Infinite Strings.

Richard A. DeMillo, Richard J. Lipton

Math. Syst. Theory, 1979

On the Complexity of Computations under Varying Sets of Primitives.

David P. Dobkin, Richard J. Lipton

J. Comput. Syst. Sci., 1979

Linear Programming is Log-Space Hard for P.

David P. Dobkin, Richard J. Lipton, Steven P. Reiss

Inf. Process. Lett., 1979

Social Processes and Proofs of Theorems and Programs.

Richard A. DeMillo, Richard J. Lipton, Alan J. Perlis

Commun. ACM, 1979

Some Connections between Mathematical Logic and Complexity Theory

Richard A. DeMillo, Richard J. Lipton

Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems

Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, Charles Rackoff

Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978

Even Data Bases That Lie Can Be Compromised.

Richard A. DeMillo, David P. Dobkin, Richard J. Lipton

IEEE Trans. Software Eng., 1978

On a political pamphlet from the middle ages.

Edsger W. Dijkstra, Richard A. DeMillo, Richard J. Lipton, Alan J. Perlis

ACM SIGSOFT Softw. Eng. Notes, 1978

Response from R. A. DeMillo, R. J. Lipton, A. J. Perlis.

Richard A. DeMillo, Richard J. Lipton, Alan J. Perlis

ACM SIGSOFT Softw. Eng. Notes, 1978

On Structure Preserving Reductions.

Nancy A. Lynch, Richard J. Lipton

SIAM J. Comput., 1978

Polynomials with 0-1 Coefficients that Are Hard to Evaluate.

Richard J. Lipton

SIAM J. Comput., 1978

Evaluation of Polynomials with Super-Preconditioning.

Richard J. Lipton, Larry J. Stockmeyer

J. Comput. Syst. Sci., 1978

The Enforcement of Security Policies for Computation.

Anita K. Jones, Richard J. Lipton

J. Comput. Syst. Sci., 1978

A Lower Bound of the ½n² on Linear Search Programs for the Knapsack Problem.

David P. Dobkin, Richard J. Lipton

J. Comput. Syst. Sci., 1978

A Batching Method for Coloring Planar Graphs.

Richard J. Lipton, Raymond E. Miller

Inf. Process. Lett., 1978

A Probabilistic Remark on Algebraic Program Testing.

Richard A. DeMillo, Richard J. Lipton

Inf. Process. Lett., 1978

Hints on Test Data Selection: Help for the Practicing Programmer.

Richard A. DeMillo, Richard J. Lipton, Frederick G. Sayward

Computer, 1978

Preserving Average Proximity in Arrays.

Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton

Commun. ACM, 1978

Model Theoretic Aspects of Computational Complexity

Richard J. Lipton

Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

Alternating Pushdown Automata (Preliminary Report)

Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer

Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

The design of a prototype mutation system for program testing.

Timothy A. Budd, Richard J. Lipton, Richard A. DeMillo, Frederick G. Sayward

Proceedings of the American Federation of Information Processing Societies: 1978 National Computer Conference, 1978

1977

Synchronization and Computing Capabilities of Linear Asynchronous Structures.

Richard J. Lipton, Raymond E. Miller, Lawrence Snyder

J. Comput. Syst. Sci., 1977

Word Problems Solvable in Logspace.

Richard J. Lipton, Yechezkel Zalcstein

J. ACM, 1977

A Linear Time Algorithm for Deciding Subject Security.

Richard J. Lipton, Lawrence Snyder

J. ACM, 1977

On the Power of Applicative Languages.

Richard J. Lipton, Lawrence Snyder

Proceedings of the Formal Description of Programming Concepts: Proceedings of the IFIP Working Conference on Formal Description of Programming Concepts, 1977

Application of a Planar Separator Theorem

Richard J. Lipton, Robert Endre Tarjan

Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977

A Necessary and Sufficient Condition for the Existence of Hoare Logics

Richard J. Lipton

Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977

1976

Complexity Measures and Hierarchies for the Evaluation of Integers and Polynomials.

Richard J. Lipton, David P. Dobkin

Theor. Comput. Sci., 1976

Can structured programs be efficient?

Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton

ACM SIGPLAN Notices, 1976

How to have your abstract rejected.

Mary-Claire Van Leunen, Richard Lipton

SIGACT News, 1976

Multidimensional Searching Problems.

David P. Dobkin, Richard J. Lipton

SIAM J. Comput., 1976

Space and Time Hierarchies for Classes of Control Structures and Data Structures.

Richard J. Lipton, Stanley C. Eisenstat, Richard A. DeMillo

J. ACM, 1976

Exponential Space Complete Problems for Petri Nets and Commutative Semigroups: Preliminary Report

E. Cardoza, Richard J. Lipton, Albert R. Meyer

Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

A Linear Time Algorithm for Deciding Security

Anita K. Jones, Richard J. Lipton, Lawrence Snyder

Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976

1975

A quantifier characterization for nondeterministic log space.

Richard J. Lipton, Nancy A. Lynch

SIGACT News, 1975

A Synchronization Anomaly.

Richard J. Lipton, Robert W. Tuttle

Inf. Process. Lett., 1975

Reduction: A Method of Proving Properties of Parallel Programs.

Richard J. Lipton

Commun. ACM, 1975

The Complexity of Control Structures and Data Structures

Richard J. Lipton, Stanley C. Eisenstat, Richard A. DeMillo

Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

Complexity Measures and Hierarchies for the Evaluation of Integers, Polynomials, and n-linear Forms

Richard J. Lipton, David P. Dobkin

Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

Reduction: A New Method of Proving Properties of Systems of Processes.

Richard J. Lipton

Proceedings of the Conference Record of the Second ACM Symposium on Principles of Programming Languages, 1975

1974

On the Aanderaa-Rosenberg Conjecture.

Richard J. Lipton, Lawrence Snyder

SIGACT News, 1974

Limitations of Synchronization Primitives with Conditional Branching and Global Variables

Richard J. Lipton

Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

On Some Generalizations of Binary Search

David P. Dobkin, Richard J. Lipton

Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

Schedulers as enforces in synchronization.

Richard J. Lipton

Proceedings of the Operating Systems, 1974

A Comparative Study of Models of Parallel Computation

Richard J. Lipton, Lawrence Snyder, Yechezkel Zalcstein

Proceedings of the 15th Annual Symposium on Switching and Automata Theory, 1974