Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Richard J. Lipton
Richard Jay Lipton
Author information
- affiliation: Georgia Institute of Technology
2010 – today
- 2013
[j71]Richard J. Lipton, Ryan Williams: Amplifying circuit lower bounds against polynomial time, with applications. Computational Complexity 22(2): 311-343 (2013)- 2012
- [j70]
- [j69]Subrahmanyam Kalyanasundaram, Richard J. Lipton, Kenneth W. Regan, Farbod Shokrieh: Improved simulation of nondeterministic Turing machines. Theor. Comput. Sci. 417: 66-73 (2012)
- [c112]Richard J. Lipton, Ryan Williams: Amplifying Circuit Lower Bounds against Polynomial Time with Applications. IEEE Conference on Computational Complexity 2012: 1-9
- [i8]Richard J. Lipton, Kenneth W. Regan, Atri Rudra: Simulating Special but Natural Quantum Circuits. CoRR abs/1201.3306 (2012)
- [i7]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
- [j68]Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai: Best-order streaming model. Theor. Comput. Sci. 412(23): 2544-2555 (2011)
- [c111]Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Richard J. Lipton, Jun (Jim) Xu: Representative skylines using threshold-based preference distributions. ICDE 2011: 387-398
- [c110]Richard J. Lipton, Kenneth W. Regan, Atri Rudra: Symmetric Functions Capture General Functions. MFCS 2011: 436-447
- [c109]Richard J. Lipton: Quantum Complexity: Some Recent Results, Some Open Problems, Some Thoughts. TAMC 2011: 171
- 2010
- [j67]Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Richard J. Lipton, Jun Xu: Regret-Minimizing Representative Databases. PVLDB 3(1): 1114-1124 (2010)
- [c108]Sang Kil Cha, Brian Pak, David Brumley, Richard Jay Lipton: Platform-independent programs. ACM Conference on Computer and Communications Security 2010: 547-558
- [c107]
- [c106]Subrahmanyam Kalyanasundaram, Richard J. Lipton, Kenneth W. Regan, Farbod Shokrieh: Improved Simulation of Nondeterministic Turing Machines. MFCS 2010: 453-464
- [i6]Jin-yi Cai, Xi Chen, Richard J. Lipton, Pinyan Lu: On Tractable Exponential Sums. CoRR abs/1005.2632 (2010)
2000 – 2009
- 2009
- [j66]Mihail N. Kolountzakis, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi: On the Fourier spectrum of symmetric Boolean functions. Combinatorica 29(3): 363-387 (2009)
- [j65]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)
- [c105]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
- [c104]Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai: Best-Order Streaming Model. TAMC 2009: 178-191
- [c103]Giovanni Di Crescenzo, Richard J. Lipton: Social Network Privacy via Evolving Access Control. WASA 2009: 551-560
- 2008
- [j64]Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton: Algorithms for Modular Counting of Roots of Multivariate Polynomials. Algorithmica 50(4): 479-496 (2008)
- [j63]Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta: Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. Algorithmica 52(1): 3-18 (2008)
- [j62]Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton: Polynomials that Sign Represent Parity and Descartes' Rule of Signs. Computational Complexity 17(3): 377-406 (2008)
- 2007
- [c102]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
- [j61]Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton: Symmetric polynomials over Zm and simultaneous communication protocols. J. Comput. Syst. Sci. 72(2): 252-285 (2006)
- [c101]Calton Pu, Steve Webb, Oleg M. Kolesnikov, Wenke Lee, Richard J. Lipton: Towards the integration of diverse spam filtering techniques. GrC 2006: 17-20
- [c100]Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton: Algorithms for Modular Counting of Roots of Multivariate Polynomials. LATIN 2006: 544-555
- [c99]Giovanni Di Crescenzo, Richard J. Lipton, Shabsi Walfish: Perfectly Secure Password Protocols in the Bounded Retrieval Model. TCC 2006: 225-244
- 2005
- [j60]Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas: Time-space lower bounds for satisfiability. J. ACM 52(6): 835-865 (2005)
- [j59]Ben Gum, Richard J. Lipton, Andrea S. LaPaugh, Faith Ellen Fich: Estimating the maximum. J. Algorithms 54(1): 105-114 (2005)
- [j58]Jun 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)
- [c98]Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi: On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas. IEEE Conference on Computational Complexity 2005: 112-119
- [c97]David Dagon, Wenke Lee, Richard J. Lipton: Protecting Secret Data from Insider Attacks. Financial Cryptography 2005: 16-30
- [c96]Subhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta: Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. WINE 2005: 92-101
- [i5]David Cash, Yan Zong Ding, Wenke Lee, Richard J. Lipton: Intrusion-Resilient Authentication in the Limited Communication Model. IACR Cryptology ePrint Archive 2005: 409 (2005)
- 2004
- [c95]Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton: Polynomials That Sign Represent Parity and Descartes Rule of Signs. IEEE Conference on Computational Complexity 2004: 223-235
- [c94]Nikhil R. Devanur, Richard J. Lipton, Nisheeth K. Vishnoi: On the Complexity of Hilbert's 17th Problem. FSTTCS 2004: 237-249
- [c93]Richard J. Lipton, Evangelos Markakis: Nash Equilibria via Polynomial Equations. LATIN 2004: 413-422
- [c92]Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, Amin Saberi: On approximately fair allocations of indivisible goods. ACM Conference on Electronic Commerce 2004: 125-131
- [i4]Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton: The Degree of Threshold Mod 6 and Diophantine Equations. Electronic Colloquium on Computational Complexity (ECCC)(022) (2004)
- 2003
- [j57]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)
- [j56]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)
- [c91]Richard J. Lipton, Anastasios Viglas: Non-uniform Depth of Polynomial Time and Space Simulations. FCT 2003: 311-320
- [c90]Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton: Symmetric Polynomials over Zm and Simultaneous Communication Protocol. FOCS 2003: 450-459
- [c89]Parikshit Gopalan, Richard J. Lipton, Aranyak Mehta: Randomized Time-Space Tradeoffs for Directed Graph Connectivity. FSTTCS 2003: 208-216
- [c88]Nikhil R. Devanur, Richard J. Lipton, Nisheeth K. Vishnoi: Who's The Weakest Link? SAGA 2003: 108-116
- [c87]Richard J. Lipton, Evangelos Markakis, Aranyak Mehta: Playing large games using simple strategies. ACM Conference on Electronic Commerce 2003: 36-41
- [c86]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. Electronic Colloquium on Computational Complexity (ECCC)(047) (2003)
- 2002
- [c85]Richard J. Lipton, S. Rajagopalan, Dimitrios N. Serpanos: Spy: A Method to Secure Clients for Network Services. ICDCS Workshops 2002: 23-28
- [c84]Alessandro Orso, Donglin Liang, Mary Jean Harrold, Richard J. Lipton: Gamma system: continuous evolution of software after deployment. ISSTA 2002: 65-69
- [c83]Jun 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. Electronic Colloquium on Computational Complexity (ECCC)(057) (2002)
- 2001
- [j55]Dan Boneh, Richard A. DeMillo, Richard J. Lipton: On the Importance of Eliminating Errors in Cryptographic Computations. J. Cryptology 14(2): 101-119 (2001)
- [c82]Dimitrios N. Serpanos, Richard J. Lipton: Defense Against Man-in-the-Middle Attack in Client-Server Systems. ISCC 2001: 9-14
- 2000
- [j54]Dirk Faulhammer, Richard J. Lipton, Laura F. Landweber: Fidelity of Enzymatic Ligation for DNA Computing. Journal of Computational Biology 7(6): 839-848 (2000)
- [j53]Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein: The Complexity of the A B C Problem. SIAM J. Comput. 29(6): 1878-1888 (2000)
- [c81]George Karakostas, Richard J. Lipton, Anastasios Viglas: On the Complexity of Intersecting Finite State Automata. IEEE Conference on Computational Complexity 2000: 229-234
1990 – 1999
- 1999
- [c80]Anna Gál, Shai Halevi, Richard J. Lipton, Erez Petrank: Computing from Partial Solutions. IEEE Conference on Computational Complexity 1999: 34-45
- [c79]
- 1998
- [j52]Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan: Reconstructing Algebraic Functions from Mixed Data. SIAM J. Comput. 28(2): 487-510 (1998)
- [c78]Richard J. Lipton, Rafail Ostrovsky: Micropayments via Efficient Coin-Flipping. Financial Cryptography 1998: 1-15
- 1997
- [c77]Dan Boneh, Richard A. DeMillo, Richard J. Lipton: On the Importance of Checking Cryptographic Protocols for Faults (Extended Abstract). EUROCRYPT 1997: 37-51
- [c76]Richard J. Lipton, Paul J. Martino, Andy Neitzke: On the Complexity of a Set-Union Problem. FOCS 1997: 110-115
- [c75]Laura F. Landweber, Richard J. Lipton: DNA²DNA Computations: A Potential "Killer App"? ICALP 1997: 56-64
- [c74]
- [c73]
- 1996
- [j51]Dan Boneh, Christopher Dunworth, Richard J. Lipton, Jiri Sgall: On the Computational Power of DNA. Discrete Applied Mathematics 71(1-3): 79-94 (1996)
- [j50]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)
- [j49]Paul Ammann, Richard J. Lipton, Ravi S. Sandhu: The Expressive Power of Multi-parent Creation in Monotonic Access Control Models. Journal of Computer Security 4(2/3): 149-166 (1996)
- [c72]Dan Boneh, Richard J. Lipton: Algorithms for Black-Box Fields and their Application to Cryptography (Extended Abstract). CRYPTO 1996: 283-297
- [c71]Masato Edahiro, Richard J. Lipton: Clock Buffer Placement Algorithm for Wire-Delay-Dominated Timing Model. Great Lakes Symposium on VLSI 1996: 143-147
- [c70]
- 1995
- [j48]Richard J. Lipton, Jeffrey F. Naughton: Query Size Estimation by Adaptive Sampling. J. Comput. Syst. Sci. 51(1): 18-25 (1995)
- [c69]Dan Boneh, Richard J. Lipton: Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract). CRYPTO 1995: 424-437
- [c68]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
- 1994
- [j47]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)
- [j46]Jin-yi Cai, Richard J. Lipton: Subquadratic Simulations of Balanced Formulae by Branching Programs. SIAM J. Comput. 23(3): 563-572 (1994)
- [c67]
- [c66]Richard J. Lipton: Some Consequences of Our Failure to Prove Non-Linear Lower Bounds on Explicit Functions. Structure in Complexity Theory Conference 1994: 79-87
- [c65]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
- [c64]
- [c63]
- [c62]Richard J. Lipton, Neal E. Young: Simple strategies for large zero-sum games with applications to complexity theory. STOC 1994: 734-740
- 1993
- [j45]Richard J. Lipton, Jeffrey F. Naughton: Clocked Adversaries for Hashing. Algorithmica 9(3): 239-252 (1993)
- [j44]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)
- [j43]Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri: Efficient Sampling Strategies for Relational Database Operations. Theor. Comput. Sci. 116(1&2): 195-226 (1993)
- [c61]Jin-yi Cai, Richard J. Lipton, Robert Sedgewick, Andrew Chi-Chih Yao: Towards Uncheatable benchmarks. Structure in Complexity Theory Conference 1993: 2-11
- [c60]
- [c59]Avrim Blum, Merrick L. Furst, Michael J. Kearns, Richard J. Lipton: Cryptographic Primitives Based on Hard Learning Problems. CRYPTO 1993: 278-291
- 1992
- [j42]Andrea S. LaPaugh, Richard J. Lipton, Jonathan S. Sandberg: How to Store a Triangular Matrix. IEEE Trans. Computers 41(7): 896-899 (1992)
- [j41]Jin-yi Cai, Anne Condon, Richard J. Lipton: On Games of Incomplete Information. Theor. Comput. Sci. 103(1): 25-38 (1992)
- [c58]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
- [c57]Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan: Reconstructing Algebraic Functions from Mixed Data. FOCS 1992: 503-512
- [c56]Kenneth Salem, Daniel Barbará, Richard J. Lipton: Probabilistic Dignosis of Hot Spots. ICDE 1992: 30-39
- 1991
- [j40]Daniel Barbará, Richard J. Lipton: A Class of Randomized Strategies for Low-Cost Comparison of File Copies. IEEE Trans. Parallel Distrib. Syst. 2(2): 160-170 (1991)
- [j39]Richard A. DeMillo, Richard J. Lipton: Defining Software by Continuous, Smooth Functions. IEEE Trans. Software Eng. 17(4): 383-384 (1991)
- [c55]Jin-yi Cai, Anne Condon, Richard J. Lipton: PSPACE Is Provable By Two Provers In One Round. Structure in Complexity Theory Conference 1991: 110-115
- [c54]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
- [j38]Richard J. Lipton, Arvin Park: The Processor Identity Problem. Inf. Process. Lett. 36(2): 91-94 (1990)
- [c53]Jin-yi Cai, Anne Condon, Richard J. Lipton: On Bounded Round Multi-Prover Interactive Proof Systems. Structure in Complexity Theory Conference 1990: 45-54
- [c52]Richard J. Lipton, Dimitrios N. Serpanos: Uniform-Cost Communication in Scalable Multiprocessors. ICPP (1) 1990: 429-432
- [c51]Richard J. Lipton, Jeffrey F. Naughton: Query Size Estimation by Adaptive Sampling. PODS 1990: 40-46
- [c50]Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider: Practical Selectivity Estimation through Adaptive Sampling. SIGMOD Conference 1990: 1-11
- [c49]Jin-yi Cai, Anne Condon, Richard J. Lipton: Playing Games of Incomplete Information. STACS 1990: 58-69
- [c48]
1980 – 1989
- 1989
- [j37]Arvin Park, Krishnaswamy Balasubramanian, Richard J. Lipton: Array Access Bounds for Block Storage Memory Systems. IEEE Trans. Computers 38(6): 909-913 (1989)
- [c47]Anne Condon, Richard J. Lipton: On the Complexity of Space Bounded Interactive Proofs (Extended Abstract). FOCS 1989: 462-467
- [c46]Jin-yi Cai, Richard J. Lipton: Subquadratic Simulations of Circuits by Branching Programs. FOCS 1989: 568-573
- [c45]Daniel Barbará, Richard J. Lipton: A Randomized Technique for Remote File Comparison. ICDCS 1989: 12-21
- [c44]Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171
- 1986
- [j36]Ravindran Kannan, Richard J. Lipton: Polynomial-time algorithm for the orbit problem. J. ACM 33(4): 808-821 (1986)
- [c43]Richard J. Lipton, Daniel P. Lopresti: Delta Transformations to Simplify VLSI Processor Arrays for Serial Dynamic Programming. ICPP 1986: 917-920
- 1985
- [j35]Merrick L. Furst, Richard J. Lipton, Larry J. Stockmeyer: Pseudorandom Number Generation and Space Complexity. Information and Control 64(1-3): 43-51 (1985)
- [j34]Ashok K. Chandra, Steven Fortune, Richard J. Lipton: Unbounded Fan-In Circuits and Associative Functions. J. Comput. Syst. Sci. 30(2): 222-234 (1985)
- [c42]Richard J. Lipton, Stephen C. North, Jonathan S. Sandberg: A method for drawing graphs. Symposium on Computational Geometry 1985: 153-160
- [c41]Richard 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
- [j33]Richard E. Ladner, Larry J. Stockmeyer, Richard J. Lipton: Alternation Bounded Auxiliary Pushdown Automata. Information and Control 62(2/3): 93-108 (1984)
- [j32]Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer: Alternating Pushdown and Stack Automata. SIAM J. Comput. 13(1): 135-155 (1984)
- [j31]Hector Garcia-Molina, Richard J. Lipton, Jacobo Valdes: A Massive Memory Machine. IEEE Trans. Computers 33(5): 391-399 (1984)
- 1983
- [j30]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)
- [c40]Andrea S. LaPaugh, Richard J. Lipton: Total stuct-at-fault testing by circuit transformation. DAC 1983: 713-716
- [c39]Merrick L. Furst, Richard J. Lipton, Larry J. Stockmeyer: Pseudorandom Number Generation and Space Complexity. FCT 1983: 171-176
- [c38]Ashok K. Chandra, Steven Fortune, Richard J. Lipton: Lower Bounds for Constant Depth Circuits for Prefix Problems. ICALP 1983: 109-117
- [c37]Andrea S. LaPaugh, Richard J. Lipton: Total Fault Testing Using the Bipartite Transformation. ITC 1983: 428-434
- [c36]Ashok K. Chandra, Steven Fortune, Richard J. Lipton: Unbounded Fan-in Circuits and Associative Functions. STOC 1983: 52-60
- [c35]
- 1982
- [c34]Richard J. Lipton, J. D. Nash: Design automation algorithms: Research and applications. DAC 1982: 410
- [c33]Richard J. Lipton, Stephen C. North, Robert Sedgewick, Jacobo Valdes, Gopalakrishnan Vijayan: ALI: A procedural language to describe VLSI layouts. DAC 1982: 467-474
- [c32]
- 1981
- [j29]Kellogg S. Booth, Richard J. Lipton: Computing Extremal and Approximate Distances in Graphs Having Unit Cost Edges. Acta Inf. 15: 319-328 (1981)
- [j28]Alon Itai, Richard J. Lipton, Christos H. Papadimitriou, Michael Rodeh: Covering Graphs by Simple Circuits. SIAM J. Comput. 10(4): 746-750 (1981)
- [j27]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)
- [c31]Richard J. Lipton, Jacobo Valdes: Census Functions: an Approach to VLSI Upper Bounds (Preliminary Version). FOCS 1981: 13-22
- [c30]George I. Davida, Richard A. DeMillo, Richard J. Lipton: Multilevel Secure Distributed System. ICDCS 1981: 308-312
- [c29]
- [e4]John White, Richard J. Lipton, Patricia C. Goldberg (Eds.): 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
- 1980
- [j26]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)
- [j25]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)
- [j24]David P. Dobkin, Richard J. Lipton: Addition Chain Methods for the Evaluation of Specific Polynomials. SIAM J. Comput. 9(1): 121-125 (1980)
- [j23]Richard J. Lipton, Robert Endre Tarjan: Applications of a Planar Separator Theorem. SIAM J. Comput. 9(3): 615-627 (1980)
- [c28]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
- [c27]George I. Davida, Richard A. DeMillo, Richard J. Lipton: Protecting Shared Cryptographic Keys. IEEE Symposium on Security and Privacy 1980: 100-102
- [c26]George I. Davida, Richard A. DeMillo, Richard J. Lipton: A System Architecture to Support a Verifiably Secure Multilevel Security System. IEEE Symposium on Security and Privacy 1980: 137-144
- [c25]Richard A. DeMillo, Richard J. Lipton: The Consistency of "P = NP" and Related Problems with Fragments of Number Theory. STOC 1980: 45-57
- [c24]
- [c23]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 (Eds.): 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
- [e2]Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, Richard J. Lipton (Eds.): Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA. ACM 1980
1970 – 1979
- 1979
- [j22]Richard A. DeMillo, Richard J. Lipton, Alan J. Perlis: Social Processes and Proofs of Theorems and Programs. Commun. ACM 22(5): 271-280 (1979)
- [j21]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)
- [j20]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)
- [j19]Richard A. DeMillo, Richard J. Lipton: A Constructive Generalization of the Borel-Cantelli Lemma with Application to the Complexity of Infinite Strings. Mathematical Systems Theory 13: 95-104 (1979)
- [j18]David P. Dobkin, Anita K. Jones, Richard J. Lipton: Secure Databases: Protection Against User Influence. ACM Trans. Database Syst. 4(1): 97-106 (1979)
- [c22]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
- [c21]Richard A. DeMillo, Richard J. Lipton: Some Connections between Mathematical Logic and Complexity Theory. STOC 1979: 153-159
- 1978
- [j17]Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton: Preserving Average Proximity in Arrays. Commun. ACM 21(3): 218-231 (1978)
- [j16]Richard J. Lipton, Raymond E. Miller: A Batching Method for Coloring Planar Graphs. Inf. Process. Lett. 7(4): 185-188 (1978)
- [j15]Richard A. DeMillo, Richard J. Lipton: A Probabilistic Remark on Algebraic Program Testing. Inf. Process. Lett. 7(4): 193-195 (1978)
- [j14]Richard J. Lipton, Larry J. Stockmeyer: Evaluation of Polynomials with Super-Preconditioning. J. Comput. Syst. Sci. 16(2): 124-139 (1978)
- [j13]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)
- [j12]Anita K. Jones, Richard J. Lipton: The Enforcement of Security Policies for Computation. J. Comput. Syst. Sci. 17(1): 35-55 (1978)
- [j11]Richard J. Lipton: Polynomials with 0-1 Coefficients that Are Hard to Evaluate. SIAM J. Comput. 7(1): 61-69 (1978)
- [j10]Nancy A. Lynch, Richard J. Lipton: On Structure Preserving Reductions. SIAM J. Comput. 7(2): 119-126 (1978)
- [j9]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)
- [c20]Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer: Alternating Pushdown Automata (Preliminary Report). FOCS 1978: 92-106
- [c19]
- [e1]Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, Alfred V. Aho (Eds.): Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA. ACM 1978
- 1977
- [j8]Richard J. Lipton, Lawrence Snyder: A Linear Time Algorithm for Deciding Subject Security. J. ACM 24(3): 455-464 (1977)
- [j7]Richard J. Lipton, Yechezkel Zalcstein: Word Problems Solvable in Logspace. J. ACM 24(3): 522-526 (1977)
- [j6]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)
- [c18]Richard J. Lipton: A Necessary and Sufficient Condition for the Existence of Hoare Logics. FOCS 1977: 1-6
- [c17]Richard J. Lipton, Robert Endre Tarjan: Application of a Planar Separator Theorem. FOCS 1977: 162-170
- [c16]Richard A. DeMillo, Richard J. Lipton, Alan J. Perlis: Social Processes and Proofs of Theorems and Programs. POPL 1977: 206-214
- 1976
- [j5]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)
- [j4]David P. Dobkin, Richard J. Lipton: Multidimensional Searching Problems. SIAM J. Comput. 5(2): 181-186 (1976)
- [j3]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
- [j2]Richard J. Lipton: Reduction: A Method of Proving Properties of Parallel Programs. Commun. ACM 18(12): 717-721 (1975)
- [j1]Richard J. Lipton, Robert W. Tuttle: A Synchronization Anomaly. Inf. Process. Lett. 3(3): 65-66 (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]
- [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
- [c4]Richard J. Lipton, Lawrence Snyder, Yechezkel Zalcstein: A Comparative Study of Models of Parallel Computation. SWAT (FOCS) 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]
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-05-20 20:30 CEST by the dblp team