default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDRichard J. Lipton
Richard Jay Lipton – Richard Lipton 0001
Person information
- affiliation: Georgia Institute of Technology
- affiliation: Princeton University, USA
- award (2014): Knuth Prize
Other persons with the same name
- Richard B. Lipton (aka: Richard Lipton 0002) — Albert Einstein College of Medicine, New York, NY, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2022
[c128]Richard Lipton, Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser, James Worrell:
On the Skolem Problem and the Skolem Conjecture. LICS 2022: 5:1-5:9- 2020
- [c127]George Kenison
, Richard Lipton, Joël Ouaknine, James Worrell:
On the skolem problem and prime powers. ISSAC 2020: 289-296 - [i10]George Kenison, Richard Lipton, Joël Ouaknine, James Worrell:
On the Skolem Problem and Prime Powers. CoRR abs/2006.07432 (2020)
2010 – 2019
- 2016
- [c126]Richard J. Lipton, Rafail Ostrovsky, Vassilis Zikas:
Provably Secure Virus Detection: Using The Observer Effect Against Malware. ICALP 2016: 32:1-32:14 - [c125]Alexandra Boldyreva, Taesoo Kim, Richard J. Lipton, Bogdan Warinschi:
Provably-Secure Remote Memory Attestation for Heap Overflow Protection. SCN 2016: 83-103 - 2015
- [i9]Richard J. Lipton, Rafail Ostrovsky, Vassilis Zikas:
Provable Virus Detection: Using the Uncertainty Principle to Protect Against Malware. IACR Cryptol. ePrint Arch. 2015: 728 (2015) - [i8]Alexandra Boldyreva, Taesoo Kim, Richard J. Lipton, Bogdan Warinschi:
Towards Provably-Secure Remote Memory Attestation. IACR Cryptol. ePrint Arch. 2015: 729 (2015) - 2013
- [b1]Richard J. Lipton, Kenneth W. Regan:
People, Problems, and Proofs - Essays from Gödel's Lost Letter: 2010. Springer 2013, ISBN 978-3-642-41421-3, pp. I-XVIII, 1-333 - [j85]Richard J. Lipton, Ryan Williams:
Amplifying circuit lower bounds against polynomial time, with applications. Comput. Complex. 22(2): 311-343 (2013) - [j84]Parinya Chalermsook, Shiva Kintali, Richard J. Lipton, Danupon Nanongkai:
Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs. Chic. J. Theor. Comput. Sci. 2013 (2013) - [j83]Atish Das Sarma, Amita Gajewar, Richard J. Lipton, Danupon Nanongkai:
An Approximate Restatement of the Four-Color Theorem. J. Graph Algorithms Appl. 17(5): 567-573 (2013) - 2012
- [j82]Richard J. Lipton:
Might Turing Have Won a Turing Award? Computer 45(6): 96-97 (2012) - [j81]Subrahmanyam Kalyanasundaram, Richard J. Lipton, Kenneth W. Regan, Farbod Shokrieh:
Improved simulation of nondeterministic Turing machines. Theor. Comput. Sci. 417: 66-73 (2012) - [c124]Richard J. Lipton, Ryan Williams:
Amplifying Circuit Lower Bounds against Polynomial Time with Applications. CCC 2012: 1-9 - [i7]Richard J. Lipton, Kenneth W. Regan, Atri Rudra:
Simulating Special but Natural Quantum Circuits. CoRR abs/1201.3306 (2012) - [i6]Parinya Chalermsook, Shiva Kintali, Richard J. Lipton, Danupon Nanongkai:
Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs. CoRR abs/1203.1940 (2012) - 2011
- [j80]Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai:
Best-order streaming model. Theor. Comput. Sci. 412(23): 2544-2555 (2011) - [c123]Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Richard J. Lipton, Jun (Jim) Xu:
Representative skylines using threshold-based preference distributions. ICDE 2011: 387-398 - [c122]Richard J. Lipton, Kenneth W. Regan, Atri Rudra:
Symmetric Functions Capture General Functions. MFCS 2011: 436-447 - [c121]Richard J. Lipton:
Quantum Complexity: Some Recent Results, Some Open Problems, Some Thoughts. TAMC 2011: 171 - 2010
- [j79]Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Richard J. Lipton, Jun (Jim) Xu:
Regret-Minimizing Representative Databases. Proc. VLDB Endow. 3(1): 1114-1124 (2010) - [c120]Sang Kil Cha, Brian Pak, David Brumley, Richard Jay Lipton:
Platform-independent programs. CCS 2010: 547-558 - [c119]Jin-yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu:
On Tractable Exponential Sums. FAW 2010: 148-159 - [c118]Subrahmanyam Kalyanasundaram, Richard J. Lipton, Kenneth W. Regan, Farbod Shokrieh:
Improved Simulation of Nondeterministic Turing Machines. MFCS 2010: 453-464 - [i5]Jin-yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu:
On Tractable Exponential Sums. CoRR abs/1005.2632 (2010)
2000 – 2009
- 2009
- [j78]Mihail N. Kolountzakis, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi:
On the Fourier spectrum of symmetric Boolean functions. Comb. 29(3): 363-387 (2009) - [j77]Markus Bläser, Moritz Hardt, Richard J. Lipton, Nisheeth K. Vishnoi:
Deterministically testing sparse polynomial identities of unbounded degree. Inf. Process. Lett. 109(3): 187-192 (2009) - [c117]Mostafa H. Ammar, Deeparnab Chakrabarty, Atish Das Sarma, Subrahmanyam Kalyanasundaram, Richard J. Lipton:
Algorithms for Message Ferrying on Mobile ad hoc Networks. FSTTCS 2009: 13-24 - [c116]Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai:
Best-Order Streaming Model. TAMC 2009: 178-191 - [c115]Giovanni Di Crescenzo, Richard J. Lipton:
Social Network Privacy via Evolving Access Control. WASA 2009: 551-560 - 2008
- [j76]Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton:
Algorithms for Modular Counting of Roots of Multivariate Polynomials. Algorithmica 50(4): 479-496 (2008) - [j75]Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta:
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. Algorithmica 52(1): 3-18 (2008) - [j74]Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton:
Polynomials that Sign Represent Parity and Descartes' Rule of Signs. Comput. Complex. 17(3): 377-406 (2008) - 2007
- [c114]David Cash, Yan Zong Ding, Yevgeniy Dodis, Wenke Lee, Richard J. Lipton, Shabsi Walfish:
Intrusion-Resilient Key Exchange in the Bounded Retrieval Model. TCC 2007: 479-498 - 2006
- [j73]Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton:
Symmetric polynomials over Zm and simultaneous communication protocols. J. Comput. Syst. Sci. 72(2): 252-285 (2006) - [c113]Calton Pu, Steve Webb, Oleg M. Kolesnikov, Wenke Lee, Richard J. Lipton:
Towards the integration of diverse spam filtering techniques. GrC 2006: 17-20 - [c112]Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton:
Algorithms for Modular Counting of Roots of Multivariate Polynomials. LATIN 2006: 544-555 - [c111]Giovanni Di Crescenzo, Richard J. Lipton, Shabsi Walfish:
Perfectly Secure Password Protocols in the Bounded Retrieval Model. TCC 2006: 225-244 - 2005
- [j72]Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas:
Time-space lower bounds for satisfiability. J. ACM 52(6): 835-865 (2005) - [j71]Ben Gum, Richard J. Lipton, Andrea S. LaPaugh, Faith E. Fich:
Estimating the maximum. J. Algorithms 54(1): 105-114 (2005) - [j70]Jun (Jim) Xu, Richard J. Lipton:
On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms. IEEE/ACM Trans. Netw. 13(1): 15-28 (2005) - [c110]Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi:
On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas. CCC 2005: 112-119 - [c109]David Dagon, Wenke Lee, Richard J. Lipton:
Protecting Secret Data from Insider Attacks. Financial Cryptography 2005: 16-30 - [c108]Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta:
Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. WINE 2005: 92-101 - 2004
- [c107]Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton:
Polynomials That Sign Represent Parity and Descartes Rule of Signs. CCC 2004: 223-235 - [c106]Nikhil R. Devanur, Richard J. Lipton, Nisheeth K. Vishnoi:
On the Complexity of Hilbert's 17th Problem. FSTTCS 2004: 237-249 - [c105]Richard J. Lipton, Evangelos Markakis:
Nash Equilibria via Polynomial Equations. LATIN 2004: 413-422 - [c104]Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, Amin Saberi:
On approximately fair allocations of indivisible goods. EC 2004: 125-131 - [i4]Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton:
The Degree of Threshold Mod 6 and Diophantine Equations. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j69]Richard J. Lipton, Mitsunori Ogihara, Yechezkel Zalcstein:
A Note on Square Rooting of Time Functions of Turing Machines. Theory Comput. Syst. 36(3): 295-299 (2003) - [j68]George Karakostas, Richard J. Lipton, Anastasios Viglas:
On the complexity of intersecting finite state automata and N L versus N P. Theor. Comput. Sci. 302(1-3): 257-274 (2003) - [c103]Richard J. Lipton, Anastasios Viglas:
Non-uniform Depth of Polynomial Time and Space Simulations. FCT 2003: 311-320 - [c102]Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton:
Symmetric Polynomials over Zm and Simultaneous Communication Protocol. FOCS 2003: 450-459 - [c101]Parikshit Gopalan, Richard J. Lipton, Aranyak Mehta:
Randomized Time-Space Tradeoffs for Directed Graph Connectivity. FSTTCS 2003: 208-216 - [c100]Jun Xu, Richard J. Lipton, Irfan A. Essa, Minho Sung, Yong Zhu:
Mandatory human participation: a new authentication scheme for building secure systems. ICCCN 2003: 547-552 - [c99]Nikhil R. Devanur, Richard J. Lipton, Nisheeth K. Vishnoi:
Who's The Weakest Link? SAGA 2003: 108-116 - [c98]Richard J. Lipton, Evangelos Markakis, Aranyak Mehta:
Playing large games using simple strategies. EC 2003: 36-41 - [c97]Richard J. Lipton, Nisheeth K. Vishnoi:
Deterministic identity testing for multivariate polynomials. SODA 2003: 756-760 - [i3]Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton:
Symmetric Polynomials over Zm and Simultaneous Communication Protocols. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [j67]Richard J. Lipton, S. Raj Rajagopalan, Dimitrios Serpanos:
Network and service security. IEEE Netw. 16(6): 6 (2002) - [c96]Richard J. Lipton, S. Raj Rajagopalan, Dimitrios N. Serpanos:
Spy: A Method to Secure Clients for Network Services. ICDCS Workshops 2002: 23-28 - [c95]Alessandro Orso, Donglin Liang, Mary Jean Harrold, Richard J. Lipton:
Gamma system: continuous evolution of software after deployment. ISSTA 2002: 65-69 - [c94]Jun (Jim) Xu, Richard J. Lipton:
On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms. SIGCOMM 2002: 279-292 - [i2]Richard J. Lipton, Neal E. Young:
Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory. CoRR cs.CC/0205035 (2002) - [i1]Richard J. Lipton, Anastasios Viglas:
Non-uniform Depth of Polynomial Time and Space Simulations. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [j66]Dan Boneh, Richard A. DeMillo, Richard J. Lipton:
On the Importance of Eliminating Errors in Cryptographic Computations. J. Cryptol. 14(2): 101-119 (2001) - [c93]Dimitrios N. Serpanos, Richard J. Lipton:
Defense Against Man-in-the-Middle Attack in Client-Server Systems. ISCC 2001: 9-14 - [c92]Ben Gum, Richard J. Lipton:
Cheaper by the Dozen: Batched Algorithms. SDM 2001: 1-11 - 2000
- [j65]Dirk Faulhammer, Richard J. Lipton, Laura F. Landweber:
Fidelity of Enzymatic Ligation for DNA Computing. J. Comput. Biol. 7(6): 839-848 (2000) - [j64]Dirk Faulhammer, Anthony R. Cukras, Richard J. Lipton, Laura F. Landweber:
Molecular computation: RNA solutions to chess problems. Proc. Natl. Acad. Sci. USA 97(4): 1385-1389 (2000) - [j63]Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein:
The Complexity of the A B C Problem. SIAM J. Comput. 29(6): 1878-1888 (2000) - [c91]George Karakostas, Richard J. Lipton, Anastasios Viglas:
On the Complexity of Intersecting Finite State Automata. CCC 2000: 229-234
1990 – 1999
- 1999
- [c90]Anna Gál, Shai Halevi, Richard J. Lipton, Erez Petrank:
Computing from Partial Solutions. CCC 1999: 34-45 - [c89]Dirk Faulhammer, Anthony R. Cukras, Richard J. Lipton, Laura F. Landweber:
When the Knight falls: On constructing an RNA computer. DNA Based Computers 1999: 1-7 - [c88]Richard J. Lipton, Anastasios Viglas:
On the Complexity of SAT. FOCS 1999: 459-464 - 1998
- [j62]Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan:
Reconstructing Algebraic Functions from Mixed Data. SIAM J. Comput. 28(2): 487-510 (1998) - [c87]Richard J. Lipton, Rafail Ostrovsky:
Micropayments via Efficient Coin-Flipping. Financial Cryptography 1998: 1-15 - 1997
- [c86]Laura F. Landweber, Richard J. Lipton, Michael O. Rabin:
DNA2DNA computations: A potential "killer app?". DNA Based Computers 1997: 161-172 - [c85]Dan Boneh, Richard A. DeMillo, Richard J. Lipton:
On the Importance of Checking Cryptographic Protocols for Faults (Extended Abstract). EUROCRYPT 1997: 37-51 - [c84]Richard J. Lipton, Paul J. Martino, Andy Neitzke:
On the Complexity of a Set-Union Problem. FOCS 1997: 110-115 - [c83]Laura F. Landweber, Richard J. Lipton:
DNA²DNA Computations: A Potential "Killer App"? ICALP 1997: 56-64 - [c82]Dan Boneh, Richard J. Lipton:
Effect of Operators on Straight Line Complexity. ISTCS 1997: 1-5 - [c81]Richard J. Lipton:
DNA2DNA Computation: A Potential Killer Application? NIPS 1997 - 1996
- [j61]Dan Boneh, Christopher Dunworth, Richard J. Lipton, Jirí Sgall:
On the Computational Power of DNA. Discret. Appl. Math. 71(1-3): 79-94 (1996) - [j60]Richard J. Lipton:
On Proving that a Graph has no Large Clique: A Connection with Ramsey Theory. Inf. Process. Lett. 58(1): 39-42 (1996) - [j59]Paul Ammann, Richard J. Lipton, Ravi S. Sandhu:
The Expressive Power of Multi-parent Creation in Monotonic Access Control Models. J. Comput. Secur. 4(2/3): 149-166 (1996) - [c80]Dan Boneh, Richard J. Lipton:
Algorithms for Black-Box Fields and their Application to Cryptography (Extended Abstract). CRYPTO 1996: 283-297 - [c79]Dan Boneh, Christopher Dunworth, Richard J. Lipton, Jirí Sgall:
Making DNA computers error resistant. DNA Based Computers 1996: 163-170 - [c78]Richard J. Lipton:
DNA computations can have global memory. DNA Based Computers 1996: 259-265 - [c77]Masato Edahiro, Richard J. Lipton:
Clock Buffer Placement Algorithm for Wire-Delay-Dominated Timing Model. Great Lakes Symposium on VLSI 1996: 143-147 - [c76]Richard J. Lipton:
DNA computations can have global memory. ICCD 1996: 344-347 - [c75]Dan Boneh, Richard J. Lipton:
A Revocable Backup System. USENIX Security Symposium 1996 - 1995
- [j58]Richard J. Lipton, Jeffrey F. Naughton:
Query Size Estimation by Adaptive Sampling. J. Comput. Syst. Sci. 51(1): 18-25 (1995) - [c74]Dan Boneh, Richard J. Lipton:
Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract). CRYPTO 1995: 424-437 - [c73]Dan Boneh, Christopher Dunworth, Richard J. Lipton:
Breaking DES using a molecular computer. DNA Based Computers 1995: 37-65 - [c72]Richard J. Lipton:
Speeding up computations via molecular biology. DNA Based Computers 1995: 67-74 - [c71]Jin-yi Cai, Richard J. Lipton, Luc Longpré, Mitsunori Ogihara, Kenneth W. Regan, D. Sivakumar:
Communication Complexity of Key Agreement on Small Ranges. STACS 1995: 38-49 - [e5]Richard J. Lipton, Eric B. Baum:
DNA Based Computers, Proceedings of a DIMACS Workshop, Princeton, New Jersey, USA, April 4, 1995. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 27, DIMACS/AMS 1995, ISBN 978-0-8218-0973-0 [contents] - 1994
- [j57]Jin-yi Cai, Anne Condon, Richard J. Lipton:
PSPACE Is Provable by Two Provers in One Round. J. Comput. Syst. Sci. 48(1): 183-193 (1994) - [j56]Jin-yi Cai, Richard J. Lipton:
Subquadratic Simulations of Balanced Formulae by Branching Programs. SIAM J. Comput. 23(3): 563-572 (1994) - [c70]Richard J. Lipton:
Straight-line complexity and integer factorization. ANTS 1994: 71-79 - [c69]Richard J. Lipton:
Some Consequences of Our Failure to Prove Non-Linear Lower Bounds on Explicit Functions. SCT 1994: 79-87 - [c68]Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein:
The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices. FOCS 1994: 135-142 - [c67]Richard J. Lipton, Andrew Tomkins:
Online Interval Scheduling. SODA 1994: 302-311 - [c66]Richard J. Lipton:
A New Approach To Information Theory. STACS 1994: 699-708 - [c65]Richard J. Lipton, Neal E. Young:
Simple strategies for large zero-sum games with applications to complexity theory. STOC 1994: 734-740 - 1993
- [j55]Richard J. Lipton, Jeffrey F. Naughton:
Clocked Adversaries for Hashing. Algorithmica 9(3): 239-252 (1993) - [j54]Narendra Karmarkar, Richard M. Karp, Richard J. Lipton, László Lovász, Michael Luby:
A Monte-Carlo Algorithm for Estimating the Permanent. SIAM J. Comput. 22(2): 284-293 (1993) - [j53]Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri:
Efficient Sampling Strategies for Relational Database Operations. Theor. Comput. Sci. 116(1): 195-226 (1993) - [c64]Jin-yi Cai, Richard J. Lipton, Robert Sedgewick, Andrew Chi-Chih Yao:
Towards Uncheatable benchmarks. SCT 1993: 2-11 - [c63]Dan Boneh, Richard J. Lipton:
Amplification of Weak Learning under the Uniform Distribution. COLT 1993: 347-351 - [c62]Avrim Blum, Merrick L. Furst, Michael J. Kearns, Richard J. Lipton:
Cryptographic Primitives Based on Hard Learning Problems. CRYPTO 1993: 278-291 - 1992
- [j52]Andrea S. LaPaugh, Richard J. Lipton, Jonathan S. Sandberg:
How to Store a Triangular Matrix. IEEE Trans. Computers 41(7): 896-899 (1992) - [j51]Jin-yi Cai, Anne Condon, Richard J. Lipton:
On Games of Incomplete Information. Theor. Comput. Sci. 103(1): 25-38 (1992) - [c61]Paul Ammann, Richard J. Lipton, Ravi S. Sandhu:
The Expressive Power of Multi-Parent Creation in a Monotonic Access Control Model. CSFW 1992: 148-156 - [c60]Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan:
Reconstructing Algebraic Functions from Mixed Data. FOCS 1992: 503-512 - [c59]Kenneth Salem, Daniel Barbará, Richard J. Lipton:
Probabilistic Dignosis of Hot Spots. ICDE 1992: 30-39 - 1991
- [j50]Noga Alon, Daniel J. Kleitman, Richard J. Lipton, Roy Meshulam, Michael O. Rabin, Joel H. Spencer:
Set systems with no union of cardinality 0 modulom. Graphs Comb. 7(2): 97-99 (1991) - [j49]Daniel Barbará, Richard J. Lipton:
A Class of Randomized Strategies for Low-Cost Comparison of File Copies. IEEE Trans. Parallel Distributed Syst. 2(2): 160-170 (1991) - [j48]Richard A. DeMillo, Richard J. Lipton:
Defining Software by Continuous, Smooth Functions. IEEE Trans. Software Eng. 17(4): 383-384 (1991) - [c58]Jin-yi Cai, Anne Condon, Richard J. Lipton:
PSPACE Is Provable By Two Provers In One Round. SCT 1991: 110-115 - [c57]Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson:
Self-Testing/Correcting for Polynomials and for Approximate Functions. STOC 1991: 32-42 - 1990
- [j47]Richard J. Lipton, Arvin Park:
The Processor Identity Problem. Inf. Process. Lett. 36(2): 91-94 (1990) - [j46]Arvin Park, Jeffrey C. Becker, Richard J. Lipton:
IOStone: a synthetic file system benchmark. SIGARCH Comput. Archit. News 18(2): 45-52 (1990) - [c56]Jin-yi Cai, Anne Condon, Richard J. Lipton:
On Bounded Round Multi-Prover Interactive Proof Systems. SCT 1990: 45-54 - [c55]Richard J. Lipton, Dimitrios N. Serpanos:
Uniform-Cost Communication in Scalable Multiprocessors. ICPP (1) 1990: 429-432 - [c54]Richard J. Lipton, Jeffrey F. Naughton:
Query Size Estimation by Adaptive Sampling. PODS 1990: 40-46 - [c53]Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider:
Practical Selectivity Estimation through Adaptive Sampling. SIGMOD Conference 1990: 1-11 - [c52]Jin-yi Cai, Anne Condon, Richard J. Lipton:
Playing Games of Incomplete Information. STACS 1990: 58-69 - [c51]Richard J. Lipton:
Efficient Checking of Computations. STACS 1990: 207-215
1980 – 1989
- 1989
- [j45]Arvin Park, Krishnaswamy Balasubramanian, Richard J. Lipton:
Array Access Bounds for Block Storage Memory Systems. IEEE Trans. Computers 38(6): 909-913 (1989) - [c50]Richard J. Lipton:
New Directions In Testing. Distributed Computing And Cryptography 1989: 191-202 - [c49]Anne Condon, Richard J. Lipton:
On the Complexity of Space Bounded Interactive Proofs (Extended Abstract). FOCS 1989: 462-467 - [c48]Jin-yi Cai, Richard J. Lipton:
Subquadratic Simulations of Circuits by Branching Programs. FOCS 1989: 568-573 - [c47]Daniel Barbará, Richard J. Lipton:
A Randomized Technique for Remote File Comparison. ICDCS 1989: 12-21 - [c46]Richard J. Lipton, Jeffrey F. Naughton:
Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171 - 1986
- [j44]Ravindran Kannan, Richard J. Lipton:
Polynomial-time algorithm for the orbit problem. J. ACM 33(4): 808-821 (1986) - [c45]Richard J. Lipton, Daniel P. Lopresti:
Delta Transformations to Simplify VLSI Processor Arrays for Serial Dynamic Programming. ICPP 1986: 917-920 - 1985
- [j43]Merrick L. Furst, Richard J. Lipton, Larry J. Stockmeyer:
Pseudorandom Number Generation and Space Complexity. Inf. Control. 64(1-3): 43-51 (1985) - [j42]Ashok K. Chandra, Steven Fortune, Richard J. Lipton:
Unbounded Fan-In Circuits and Associative Functions. J. Comput. Syst. Sci. 30(2): 222-234 (1985) - [c44]Richard J. Lipton, Stephen C. North, Jonathan S. Sandberg:
A method for drawing graphs. SCG 1985: 153-160 - [c43]Richard E. Cullingford, Hector Garcia-Molina, Richard J. Lipton:
The Role Of Massive Memory In Knowledge-Base Management Systems. On Knowledge Base Management Systems (Islamorada) 1985: 535-550 - 1984
- [j41]Richard E. Ladner, Larry J. Stockmeyer, Richard J. Lipton:
Alternation Bounded Auxiliary Pushdown Automata. Inf. Control. 62(2/3): 93-108 (1984) - [j40]Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer:
Alternating Pushdown and Stack Automata. SIAM J. Comput. 13(1): 135-155 (1984) - [j39]Hector Garcia-Molina, Richard J. Lipton, Jacobo Valdes:
A Massive Memory Machine. IEEE Trans. Computers 33(5): 391-399 (1984) - 1983
- [j38]Richard J. Lipton, Jacobo Valdes, Gopalakrishnan Vijayan, Stephen C. North, Robert Sedgewick:
VLSI Layout as Programming. ACM Trans. Program. Lang. Syst. 5(3): 405-421 (1983) - [c42]Andrea S. LaPaugh, Richard J. Lipton:
Total stuct-at-fault testing by circuit transformation. DAC 1983: 713-716 - [c41]Merrick L. Furst, Richard J. Lipton, Larry J. Stockmeyer:
Pseudorandom Number Generation and Space Complexity. FCT 1983: 171-176 - [c40]Ashok K. Chandra, Steven Fortune, Richard J. Lipton:
Lower Bounds for Constant Depth Circuits for Prefix Problems. ICALP 1983: 109-117 - [c39]Andrea S. LaPaugh, Richard J. Lipton:
Total Fault Testing Using the Bipartite Transformation. ITC 1983: 428-434 - [c38]Ashok K. Chandra, Steven Fortune, Richard J. Lipton:
Unbounded Fan-in Circuits and Associative Functions. STOC 1983: 52-60 - [c37]Ashok K. Chandra, Merrick L. Furst, Richard J. Lipton:
Multi-Party Protocols. STOC 1983: 94-99 - 1982
- [c36]Richard J. Lipton, J. Daniel Nash:
Design automation algorithms: Research and applications. DAC 1982: 410 - [c35]Richard J. Lipton, Stephen C. North, Robert Sedgewick, Jacobo Valdes, Gopalakrishnan Vijayan:
ALI: A procedural language to describe VLSI layouts. DAC 1982: 467-474 - [c34]Richard J. Lipton, Robert Sedgewick, Jacobo Valdes:
Programming Aspects of VLSI. POPL 1982: 57-65 - 1981
- [j37]Kellogg S. Booth, Richard J. Lipton:
Computing Extremal and Approximate Distances in Graphs Having Unit Cost Edges. Acta Informatica 15: 319-328 (1981) - [j36]Alon Itai, Richard J. Lipton, Christos H. Papadimitriou, Michael Rodeh:
Covering Graphs by Simple Circuits. SIAM J. Comput. 10(4): 746-750 (1981) - [j35]Lawrence H. Landweber, Richard J. Lipton, Edward L. Robertson:
On the Structure of Sets in NP and Other Complexity Classes. Theor. Comput. Sci. 15: 181-200 (1981) - [c33]Richard J. Lipton, Jacobo Valdes:
Census Functions: an Approach to VLSI Upper Bounds (Preliminary Version). FOCS 1981: 13-22 - [c32]George I. Davida, Richard A. DeMillo, Richard J. Lipton:
Multilevel Secure Distributed System. ICDCS 1981: 308-312 - [c31]Richard J. Lipton, Robert Sedgewick:
Lower Bounds for VLSI. STOC 1981: 300-307 - [e4]John White, Richard J. Lipton, Patricia C. Goldberg:
Conference Record of the Eighth Annual ACM Symposium on Principles of Programming Languages, Williamsburg, Virginia, USA, January 1981. ACM Press 1981, ISBN 0-89791-029-X [contents] - 1980
- [j34]Richard J. Lipton, Arnold L. Rosenberg, Andrew Chi-Chih Yao:
External Hashing Schemes for Collections of Data Structures. J. ACM 27(1): 81-95 (1980) - [j33]Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton:
Space-Time Trade-Offs in Structured Programming: An Improved Combinatorial Embedding Theorem. J. ACM 27(1): 123-127 (1980) - [j32]David P. Dobkin, Richard J. Lipton:
Addition Chain Methods for the Evaluation of Specific Polynomials. SIAM J. Comput. 9(1): 121-125 (1980) - [j31]Richard J. Lipton, Robert Endre Tarjan:
Applications of a Planar Separator Theorem. SIAM J. Comput. 9(3): 615-627 (1980) - [c30]Timothy A. Budd, Richard A. DeMillo, Richard J. Lipton, Frederick G. Sayward:
Theoretical and Emperical Studies on Using Program Mutation to Test the Functional Correctness of Programs. POPL 1980: 220-233 - [c29]George I. Davida, Richard A. DeMillo, Richard J. Lipton:
Protecting Shared Cryptographic Keys. S&P 1980: 100-102 - [c28]George I. Davida, Richard A. DeMillo, Richard J. Lipton:
A System Architecture to Support a Verifiably Secure Multilevel Security System. S&P 1980: 137-144 - [c27]Richard A. DeMillo, Richard J. Lipton:
The Consistency of "P = NP" and Related Problems with Fragments of Number Theory. STOC 1980: 45-57 - [c26]Ravindran Kannan, Richard J. Lipton:
The Orbit Problem is Decidable. STOC 1980: 252-261 - [c25]Richard M. Karp, Richard J. Lipton:
Some Connections between Nonuniform and Uniform Complexity Classes. STOC 1980: 302-309 - [e3]Paul W. Abrahams, Richard J. Lipton, Stephen R. Bourne:
Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, Las Vegas, Nevada, USA, January 1980. ACM Press 1980, ISBN 0-89791-011-7 [contents] - [e2]Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, Richard J. Lipton:
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA. ACM 1980 [contents]
1970 – 1979
- 1979
- [j30]Richard A. DeMillo, Richard J. Lipton, Alan J. Perlis:
Social Processes and Proofs of Theorems and Programs. Commun. ACM 22(5): 271-280 (1979) - [j29]David P. Dobkin, Richard J. Lipton, Steven P. Reiss:
Linear Programming is Log-Space Hard for P. Inf. Process. Lett. 8(2): 96-97 (1979) - [j28]David P. Dobkin, Richard J. Lipton:
On the Complexity of Computations under Varying Sets of Primitives. J. Comput. Syst. Sci. 18(1): 86-91 (1979) - [j27]Richard A. DeMillo, Richard J. Lipton:
A Constructive Generalization of the Borel-Cantelli Lemma with Application to the Complexity of Infinite Strings. Math. Syst. Theory 13: 95-104 (1979) - [j26]Richard A. DeMillo, Richard J. Lipton:
Review of "Proofs and refutations: the logic of mathematical discovery" by Imre Lakatos. Cambridge University Press 1976. SIGACT News 11(2): 7-9 (1979) - [j25]David P. Dobkin, Anita K. Jones, Richard J. Lipton:
Secure Databases: Protection Against User Influence. ACM Trans. Database Syst. 4(1): 97-106 (1979) - [c24]Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, Charles Rackoff:
Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. FOCS 1979: 218-223 - [c23]Richard A. DeMillo, Richard J. Lipton:
Some Connections between Mathematical Logic and Complexity Theory. STOC 1979: 153-159 - 1978
- [j24]Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton:
Preserving Average Proximity in Arrays. Commun. ACM 21(3): 218-231 (1978) - [j23]Richard A. DeMillo, Richard J. Lipton, Frederick G. Sayward:
Hints on Test Data Selection: Help for the Practicing Programmer. Computer 11(4): 34-41 (1978) - [j22]Richard J. Lipton, Raymond E. Miller:
A Batching Method for Coloring Planar Graphs. Inf. Process. Lett. 7(4): 185-188 (1978) - [j21]Richard A. DeMillo, Richard J. Lipton:
A Probabilistic Remark on Algebraic Program Testing. Inf. Process. Lett. 7(4): 193-195 (1978) - [j20]Richard J. Lipton, Larry J. Stockmeyer:
Evaluation of Polynomials with Super-Preconditioning. J. Comput. Syst. Sci. 16(2): 124-139 (1978) - [j19]David P. Dobkin, Richard J. Lipton:
A Lower Bound of the ½n² on Linear Search Programs for the Knapsack Problem. J. Comput. Syst. Sci. 16(3): 413-417 (1978) - [j18]Anita K. Jones, Richard J. Lipton:
The Enforcement of Security Policies for Computation. J. Comput. Syst. Sci. 17(1): 35-55 (1978) - [j17]Richard J. Lipton:
Polynomials with 0-1 Coefficients that Are Hard to Evaluate. SIAM J. Comput. 7(1): 61-69 (1978) - [j16]Nancy A. Lynch, Richard J. Lipton:
On Structure Preserving Reductions. SIAM J. Comput. 7(2): 119-126 (1978) - [j15]Edsger W. Dijkstra, Richard A. DeMillo, Richard J. Lipton, Alan J. Perlis:
On a political pamphlet from the middle ages. ACM SIGSOFT Softw. Eng. Notes 3(2): 14-16 (1978) - [j14]Richard A. DeMillo, Richard J. Lipton, Alan J. Perlis:
Response from R. A. DeMillo, R. J. Lipton, A. J. Perlis. ACM SIGSOFT Softw. Eng. Notes 3(2): 16-17 (1978) - [j13]Richard A. DeMillo, David P. Dobkin, Richard J. Lipton:
Even Data Bases That Lie Can Be Compromised. IEEE Trans. Software Eng. 4(1): 73-75 (1978) - [c22]Timothy A. Budd, Richard J. Lipton, Richard A. DeMillo, Frederick G. Sayward:
The design of a prototype mutation system for program testing. AFIPS National Computer Conference 1978: 623-629 - [c21]Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer:
Alternating Pushdown Automata (Preliminary Report). FOCS 1978: 92-106 - [c20]Richard J. Lipton:
Model Theoretic Aspects of Computational Complexity. FOCS 1978: 193-200 - [e1]Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, Alfred V. Aho:
Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA. ACM 1978 [contents] - 1977
- [j12]Richard J. Lipton, Lawrence Snyder:
A Linear Time Algorithm for Deciding Subject Security. J. ACM 24(3): 455-464 (1977) - [j11]Richard J. Lipton, Yechezkel Zalcstein:
Word Problems Solvable in Logspace. J. ACM 24(3): 522-526 (1977) - [j10]Richard J. Lipton, Raymond E. Miller, Lawrence Snyder:
Synchronization and Computing Capabilities of Linear Asynchronous Structures. J. Comput. Syst. Sci. 14(1): 49-72 (1977) - [c19]Richard J. Lipton:
A Necessary and Sufficient Condition for the Existence of Hoare Logics. FOCS 1977: 1-6 - [c18]Richard J. Lipton, Robert Endre Tarjan:
Application of a Planar Separator Theorem. FOCS 1977: 162-170 - [c17]Richard J. Lipton, Lawrence Snyder:
On the Power of Applicative Languages. Formal Description of Programming Concepts 1977: 203-210 - [c16]Richard A. DeMillo, Richard J. Lipton, Alan J. Perlis:
Social Processes and Proofs of Theorems and Programs. POPL 1977: 206-214 - 1976
- [j9]Richard J. Lipton, Stanley C. Eisenstat, Richard A. DeMillo:
Space and Time Hierarchies for Classes of Control Structures and Data Structures. J. ACM 23(4): 720-732 (1976) - [j8]David P. Dobkin, Richard J. Lipton:
Multidimensional Searching Problems. SIAM J. Comput. 5(2): 181-186 (1976) - [j7]Mary-Claire Van Leunen, Richard Lipton:
How to have your abstract rejected. SIGACT News 8(3): 21-24 (1976) - [j6]Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton:
Can structured programs be efficient? ACM SIGPLAN Notices 11(10): 10-18 (1976) - [j5]Richard J. Lipton, David P. Dobkin:
Complexity Measures and Hierarchies for the Evaluation of Integers and Polynomials. Theor. Comput. Sci. 3(3): 349-357 (1976) - [c15]Anita K. Jones, Richard J. Lipton, Lawrence Snyder:
A Linear Time Algorithm for Deciding Security. FOCS 1976: 33-41 - [c14]David P. Dobkin, Richard J. Lipton:
A Lower Bound of ½n² on Linear Search Programs for the Knapsack Problem. MFCS 1976: 265-269 - [c13]E. Cardoza, Richard J. Lipton, Albert R. Meyer:
Exponential Space Complete Problems for Petri Nets and Commutative Semigroups: Preliminary Report. STOC 1976: 50-54 - [c12]Richard J. Lipton, Larry J. Stockmeyer:
Evaluation of Polynomials with Super-Preconditioning. STOC 1976: 174-180 - 1975
- [j4]Richard J. Lipton:
Reduction: A Method of Proving Properties of Parallel Programs. Commun. ACM 18(12): 717-721 (1975) - [j3]Richard J. Lipton, Robert W. Tuttle:
A Synchronization Anomaly. Inf. Process. Lett. 3(3): 65-66 (1975) - [j2]Richard J. Lipton, Nancy A. Lynch:
A quantifier characterization for nondeterministic log space. SIGACT News 7(4): 24-25 (1975) - [c11]David P. Dobkin, Richard J. Lipton:
On the complexity of computations under varying sets of primitives. Automata Theory and Formal Languages 1975: 110-117 - [c10]Richard J. Lipton:
Polynomials with 0-1 Coefficients that Are Hard to Evaluate. FOCS 1975: 6-10 - [c9]Richard J. Lipton, Raymond E. Miller, Lawrence Snyder:
Synchronization and Computing Capabilities of Linear Asynchronous Structures. FOCS 1975: 19-28 - [c8]Richard J. Lipton:
Reduction: A New Method of Proving Properties of Systems of Processes. POPL 1975: 78-86 - [c7]Anita K. Jones, Richard J. Lipton:
The Enforcement of Security Policies for Computation. SOSP 1975: 197-206 - [c6]Richard J. Lipton, David P. Dobkin:
Complexity Measures and Hierarchies for the Evaluation of Integers, Polynomials, and n-linear Forms. STOC 1975: 1-5 - [c5]Richard J. Lipton, Stanley C. Eisenstat, Richard A. DeMillo:
The Complexity of Control Structures and Data Structures. STOC 1975: 186-193 - 1974
- [j1]Richard J. Lipton, Lawrence Snyder:
On the Aanderaa-Rosenberg Conjecture. SIGACT News 6(1): 30-31 (1974) - [c4]Richard J. Lipton, Lawrence Snyder, Yechezkel Zalcstein:
A Comparative Study of Models of Parallel Computation. SWAT 1974: 145-155 - [c3]Richard J. Lipton:
Schedulers as enforces in synchronization. Symposium on Operating Systems 1974: 237-256 - [c2]Richard J. Lipton:
Limitations of Synchronization Primitives with Conditional Branching and Global Variables. STOC 1974: 230-241 - [c1]David P. Dobkin, Richard J. Lipton:
On Some Generalizations of Binary Search. STOC 1974: 310-316
Coauthor Index
Jin-Yi Cai
aka: Jin-yi Cai
aka: Jin-yi Cai
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-06-02 02:38 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
