×

zbMATH — the first resource for mathematics

Lipton, Richard J.

Compute Distance To:
Author ID: lipton.richard-j Recent zbMATH articles by "Lipton, Richard J."
Published as: Lipton, Richard J.; Lipton, Richard; Lipton, R. J.; Lipton, R.
Documents Indexed: 125 Publications since 1974, including 6 Books
all top 5

Co-Authors

14 single-authored
12 Dobkin, David P.
9 DeMillo, Richard A.
7 Cai, Jin-Yi
7 Regan, Kenneth W.
6 Stockmeyer, Larry J.
5 Boneh, Dan
5 Gopalan, Parikshit
5 Vishnoi, Nisheeth K.
4 Eisenstat, Stanley C.
4 Snyder, Lawrence V.
4 Tarjan, Robert Endre
3 Condon, Anne E.
3 Das Sarma, Atish
3 Furst, Merrick L.
3 Kalyanasundaram, Subrahmanyam
3 Karp, Richard Manning
3 Landweber, Laura F.
3 Markakis, Evangelos
3 Mehta, Aranyak
3 Nanongkai, Danupon
3 Naughton, Jeffrey F.
3 Viglas, Anastasios
3 Zalcstein, Yechezkel
2 Ar, Sigal
2 Bhatnagar, Nayantara
2 Chandra, Ashok K.
2 Devanur, Nikhil R.
2 Dunworth, Christopher
2 Fortune, Steven
2 Guruswami, Venkatesan
2 Jones, Anita K.
2 Ladner, Richard E.
2 LaPaugh, Andrea S.
2 Lee, Wenke
2 Miller, Raymond E.
2 Ogihara, Mitsunori
2 Rabin, Michael O.
2 Reiss, Steven P.
2 Rubinfeld, Ronitt
2 Sgall, Jiří
2 Shokrieh, Farbod
2 Sudan, Madhu
2 Walfish, Shabsi
1 Alon, Noga M.
1 Ammar, Mostafa H.
1 Basu, Saugata
1 Baum, Eric B.
1 Bläser, Markus
1 Blum, Avrim L.
1 Boldyreva, Alexandra
1 Booth, Kellogg S.
1 Cardoza, E.
1 Cash, David M.
1 Chakrabarty, Deeparnab
1 Chalermsook, Parinya
1 Chen, Xi
1 Cukras, Anthony R.
1 Dagon, David
1 Di Crescenzo, Giovanni
1 Ding, Yan Zong
1 Dodis, Yevgeniy
1 Faulhammer, Dirk
1 Fich, Faith Ellen
1 Fortnow, Lance J.
1 Gum, Ben
1 Hardt, Moritz
1 Itai, Alon
1 Kannan, Ravindran
1 Karakostas, George L.
1 Karmarkar, Narendra K.
1 Kearns, Michael Justin
1 Kenison, George
1 Khot, Subhash Ajit
1 Kim, Taesoo
1 Kintali, Shiva
1 Kleitman, Daniel J.
1 Kolountzakis, Mihail N.
1 Landweber, Lawrence H.
1 Longpré, Luc
1 Lovász, László
1 Lu, Pinyan
1 Luby, Michael G.
1 Meshulam, Roy
1 Meyer, Albert Ronald
1 North, Stephen C.
1 Ostrovsky, Rafail
1 Ouaknine, Joel O.
1 Papadimitriou, Christos Harilaos
1 Park, Arvin
1 Perlis, Alan J.
1 Robertson, Edward L.
1 Rodeh, Michael
1 Rose, Donald J.
1 Rosenberg, Arnold Leonard
1 Rudra, Atri
1 Sandberg, Jonathan S.
1 Schneider, Donovan A.
1 Spencer, Joel H.
1 Tomkins, Andrew
1 Valdes, Jacobo
...and 9 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

96 Publications have been cited 1,453 times in 1,279 Documents Cited by Year
A separator theorem for planar graphs. Zbl 0432.05022
Lipton, Richard J.; Tarjan, Robert Endre
278
1979
Applications of a planar separator theorem. Zbl 0456.68077
Lipton, Richard J.; Tarjan, Robert Endre
139
1980
Generalized nested dissection. Zbl 0435.65021
Lipton, Richard J.; Rose, Donald J.; Tarjan, Robert Endre
93
1979
A probabilistic remark on algebraic program testing. Zbl 0397.68011
DeMillo, Richard A.; Lipton, Richard J.
78
1978
Turing machines that take advice. Zbl 0529.68025
Karp, Richard M.; Lipton, Richard J.
57
1982
Alternating pushdown and stack automata. Zbl 0538.68039
Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J.
41
1984
Word problems solvable in logspace. Zbl 0359.68049
Lipton, Richard J.; Zalcstein, Yechezkel
41
1977
Online interval scheduling. Zbl 0873.68012
Lipton, Richard J.; Tomkins, Andrew
33
1994
Reduction: A method of proving properties of parallel programs. Zbl 0316.68015
Lipton, Richard J.
31
1975
Cryptographic primitives based on hard learning problems. Zbl 0870.94021
Blum, Avrim; Furst, Merrick; Kearns, Michael; Lipton, Richard J.
29
1994
On the complexity of computations under varying sets of primitives. Zbl 0409.68023
Dobkin, David P.; Lipton, Richard J.
28
1979
On the structure of sets in NP and other complexity classes. Zbl 0482.68042
Landweber, L. H.; Lipton, R. J.; Robertson, E. L.
27
1981
Multidimensional searching problems. Zbl 0333.68031
Dobkin, David; Lipton, Richard J.
27
1976
A Monte-Carlo algorithm for estimating the permanent. Zbl 0781.05034
Karmarkar, N.; Karp, R.; Lipton, R.; Lovász, László; Luby, M.
26
1993
Exponential space complete problems for Petri nets and commutative semigroups: Preliminary report. Zbl 0374.20067
Cardoza, E.; Lipton, R.; Meyer, A. R.
26
1976
Linear programming is log-space hard for P. Zbl 0402.68042
Dobkin, David; Lipton, Richard J.; Reiss, Steven
23
1979
Algorithms for black-box fields and their application to cryptography. Zbl 1329.94053
Boneh, Dan; Lipton, Richard J.
21
1996
Covering graphs by simple circuits. Zbl 0468.68071
Itai, Alon; Lipton, Richard J.; Papadimitriou, Christos H.; Rodeh, M.
20
1981
Polynomial-time algorithm for the orbit problem. Zbl 1326.68162
Kannan, R.; Lipton, R. J.
18
1986
Quantum cryptanalysis of hidden linear functions. (Extended abstract). Zbl 0876.94023
Boneh, Dan; Lipton, Richard J.
18
1995
A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem. Zbl 0397.68045
Dobkin, David; Lipton, Richard J.
18
1978
Unbounded fan-in circuits and associative functions. Zbl 0604.68051
Chandra, Ashok K.; Fortune, Steven; Lipton, Richard
17
1985
On the importance of eliminating errors in cryptographic computations. Zbl 1018.94014
Boneh, Dan; DeMillo, Richard A.; Lipton, Richard J.
17
2001
On the computational power of DNA. Zbl 0906.68071
Boneh, Dan; Dunworth, Christopher; Lipton, Richard J.; Sgall, Jiří
15
1996
Inapproximability results for combinatorial auctions with submodular utility functions. Zbl 1142.91485
Khot, Subhash; Lipton, Richard J.; Markakis, Evangelos; Mehta, Aranyak
14
2008
Simple strategies for large zero-sum games with applications to complexity theory. Zbl 1345.68175
Lipton, Richard J.; Young, Neal E.
14
1994
New directions in testing. Zbl 0722.68028
Lipton, Richard J.
14
1991
Preserving average proximity in arrays. Zbl 0378.68014
DeMillo, Richard A.; Eisenstat, Stanley C.; Lipton, Richard J.
13
1978
Perfectly secure password protocols in the bounded retrieval model. Zbl 1112.68047
Di Crescenzo, Giovanni; Lipton, Richard; Walfish, Shabsi
12
2006
Time-space lower bounds for satisfiability. Zbl 1326.68148
Fortnow, Lance; Lipton, Richard; van Melkebeek, Dieter; Viglas, Anastasios
11
2005
The processor identity problem. Zbl 0704.68007
Lipton, Richard J.; Park, Arvin
11
1990
Efficient checking of computations. Zbl 0729.68030
Lipton, Richard J.
11
1990
Making DNA computers error resistant. Zbl 0919.68031
Boneh, Dan; Dunworth, Christopher; Lipton, Richard J.; Sgall, Jiří
10
1999
A separator theorem for planar graphs. Zbl 0417.05023
Lipton, Richard J.; Tarjan, Robert E.
10
1977
Space and time hierarchies for classes of control structures and data structures. Zbl 0333.68024
Lipton, R. J.; Eisenstat, S. C.; DeMillo, R. A.
10
1976
A linear time algorithm for deciding subject security. Zbl 0358.68041
Lipton, R. J.; Snyder, L.
10
1977
A batching method for coloring planar graphs. Zbl 0395.05032
Lipton, Richard J.; Miller, Raymond E.
9
1978
Query size estimation by adaptive sampling. Zbl 0831.68035
Lipton, Richard J.; Naughton, Jeffrey F.
8
1995
Intrusion-resilient key exchange in the bounded retrieval model. Zbl 1156.94338
Cash, David; Ding, Yan Zong; Dodis, Yevgeniy; Lee, Wenke; Lipton, Richard; Walfish, Shabsi
8
2007
Turing machines that take advice. Zbl 0494.68061
Karp, Richard M.; Lipton, Richard J.
7
1982
Reconstructing algebraic functions from mixed data. Zbl 0915.68088
Ar, Sigal; Lipton, Richard J.; Rubinfeld, Ronitt; Sudan, Madhu
7
1998
PSPACE is provable by two provers in one round. Zbl 0802.68055
Cai, Jin-yi; Condon, Anne; Lipton, Richard J.
7
1994
On the Fourier spectrum of symmetric Boolean functions. Zbl 1212.42017
Kolountzakis, Mihail N.; Lipton, Richard J.; Markakis, Evangelos; Mehta, Aranyak; Vishnoi, Nisheeth K.
7
2009
Nash equilibria via polynomial equations. Zbl 1196.91012
Lipton, Richard J.; Markakis, Evangelos
7
2004
Alternation bounded auxiliary pushdown automata. Zbl 0589.68058
Ladner, Richard E.; Stockmeyer, Larry J.; Lipton, Richard J.
6
1984
On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\). Zbl 1044.68098
Karakostas, George; Lipton, Richard J.; Viglas, Anastasios
6
2003
Set systems with no union of cardinality 0 modulo \(m\). Zbl 0762.05079
Alon, N.; Kleitman, D.; Lipton, R.; Meshulam, R.; Rabin, M.; Spencer, J.
6
1991
A new approach to information theory. Zbl 0941.94501
Lipton, Richard
5
1994
Synchronization and computing capabilities of linear asynchronous structures. Zbl 0368.02038
Lipton, R. J.; Miller, R. E.; Snyder, L.
5
1977
Lower bounds for constant depth circuits for prefix problems. Zbl 0536.68051
Chandra, Ashok K.; Fortune, Steven; Lipton, Richard
4
1983
On games of incomplete information. Zbl 0757.90090
Cai, Jin-yi; Condon, Anne; Lipton, Richard J.
4
1992
Computing extremal and approximate distances in graphs having unit cost edges. Zbl 0445.90090
Booth, Kellogg S.; Lipton, Richard J.
4
1981
Addition chain methods for the evaluation of specific polynomials. Zbl 0447.68034
Dobkin, David; Lipton, Richard J.
4
1980
Social processes and proofs of theorems and programs. Zbl 0455.68017
DeMillo, Richard A.; Lipton, Richard J.; Perlis, Alan J.
4
1980
On the halting of tree replacement systems-premininary version. Zbl 0408.68046
Lipton, R. J.; Snyder, L.
4
1977
Non-uniform depth of polynomial time and space simulations. Zbl 1278.68096
Lipton, Richard J.; Viglas, Anastasios
4
2003
Straight-line complexity and integer factorization. Zbl 0842.11045
Lipton, Richard J.
4
1994
Deterministic identity testing for multivariate polynomials. Zbl 1092.68724
Lipton, Richard; Vishnoi, Nisheeth
4
2003
Playing games of incomplete information. Zbl 0786.90094
Cai, Jin-yi; Condon, Anne; Lipton, Richard J.
3
1990
Reconsructing algebraic functions from mixed data. Zbl 0925.68221
Ar, Sigal; Lipton, Richard J.; Rubinfeld, Ronitt; Sudan, Madhu
3
1992
Deterministically testing sparse polynomial identities of unbounded degree. Zbl 1191.68822
Bläser, Markus; Hardt, Moritz; Lipton, Richard J.; Vishnoi, Nisheeth K.
3
2009
Symmetric polynomials over \(\mathbb Z_{m}\) and simultaneous communication protocols. Zbl 1094.68008
Bhatnagar, Nayantara; Gopalan, Parikshit; Lipton, Richard J.
3
2006
Efficient sampling strategies for relational database operations. Zbl 0797.68048
Lipton, Richard J.; Naughton, Jeffrey F.; Schneider, Donovan A.; Seshadri, S.
3
1993
Schedulers as enforces in synchronization processes. Zbl 0309.68058
Lipton, R. J.
3
1974
On some generalizations of binary search. Zbl 0361.68063
Dobkin, David; Lipton, R. J.
3
1974
Limitations of synchronization primitives with conditional branching and global variables. Zbl 0361.68093
Lipton, R. J.
3
1974
A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem. Zbl 0362.68077
Dobkin, David; Lipton, Richard J.
3
1976
Clocked adversaries for hashing. Zbl 0787.68028
Lipton, Richard J.; Naughton, Jeffrey F.
2
1993
Space-time trade-offs in structured programming: An improved combinatorial embedding theorem. Zbl 0426.68046
DeMillo, Richard A.; Eisenstat, Stanley C.; Lipton, Richard J.
2
1980
External hashing schemes for collections of data structures. Zbl 0426.68051
Lipton, Richard J.; Rosenberg, Arnold L.; Yao, Andrew C.
2
1980
Communication complexity of key agreement on small ranges. Zbl 1379.68127
Cai, Jin-Yi; Lipton, Richard J.; Longpré, Luc; Ogihara, Mitsunori; Regan, Kenneth W.; Sivakumar, D.
2
1995
Quantum algorithms via linear algebra. A primer. Zbl 1315.68001
Lipton, Richard J.; Regan, Kenneth W.
2
2014
The complexity of the \(A\) \(B\) \(C\) problem. Zbl 0967.20029
Cai, Jin-yi; Lipton, Richard J.; Zalcstein, Yechezkel
2
2000
The \(\text{P}=\text{NP}\) question and Gödel’s lost letter. Zbl 1215.68101
Lipton, Richard J.
2
2010
On tractable exponential sums. Zbl 1288.68104
Cai, Jin-Yi; Chen, Xi; Lipton, Richard; Lu, Pinyan
2
2010
On the complexity of computations under varying sets of primitives. Zbl 0318.68034
Dobkin, David P.; Lipton, Richard J.
2
1975
Evaluation of polynomials with super-preconditioning. Zbl 0369.68031
Lipton, Richard J.; Stockmeyer, Larry J.
2
1978
Best-order streaming model. Zbl 1241.68064
Das Sarma, Atish; Lipton, Richard J.; Nanongkai, Danupon
2
2009
Homogenization and design of functionally graded composites for stiffness and strength. Zbl 1320.74091
Lipton, R.
2
2005
Pseudorandom number generation and space complexity. Zbl 0575.68048
Furst, Merrick; Lipton, Richard; Stockmeyer, Larry
1
1985
Protecting secret data from insider attacks. Zbl 1120.94314
Dagon, David; Lee, Wenke; Lipton, Richard
1
2005
Aspects of the database security problem. Zbl 0456.68133
Dobkin, David; Lipton, Richard J.; Reiss, Steven P.
1
1977
The complexity of control structures and data structures. Zbl 0408.68037
Lipton, R. J.; Eisenstat, S. C.; DeMillo, R. A.
1
1975
Addition chain methods for the evaluation of specific polynomials. Zbl 0408.68042
Dobkin, David; Lipton, Richard
1
1977
On the consistency of P=NP and fragments of arithmetic. Zbl 0419.03023
Lipton, Richard J.
1
1979
A constructive generalization of the Borel-Cantelli lemma with application to the complexity of infinite strings. Zbl 0434.03042
DeMillo, Richard A.; Lipton, Richard J.
1
1979
Algorithms for modular counting of roots of multivariate polynomials. Zbl 1143.11046
Gopalan, Parikshit; Guruswami, Venkatesan; Lipton, Richard J.
1
2008
Provably secure virus detection: using the observer effect against malware. Zbl 1388.68025
Lipton, Richard J.; Ostrovsky, Rafail; Zikas, Vassilis
1
2016
Provably-secure remote memory attestation for heap overflow protection. Zbl 1400.94123
Boldyreva, Alexandra; Kim, Taesoo; Lipton, Richard; Warinschi, Bogdan
1
2016
Subquadratic simulations of balanced formulae by branching programs. Zbl 0809.68068
Cai, Jin-Yi; Lipton, Richard J.
1
1994
Estimating the maximum. Zbl 1090.62032
Gum, Ben; Lipton, Richard J.; LaPaugh, Andrea; Fich, Faith
1
2005
When the knight falls: On constructing an RNA computer. Zbl 0970.68059
Faulhammer, Dirk; Cukras, Anthony R.; Lipton, Richard J.; Landweber, Laura F.
1
1999
Complexity measures and hierarchies for the evaluation of integers and polynomials. Zbl 0365.68049
Lipton, Richard J.; Dobkin, David
1
1977
Polynomials with 0-1 coefficients that are hard to evaluate. Zbl 0374.68039
Lipton, Richard J.
1
1978
The enforcement of security policies for computation. Zbl 0383.68034
Jones, Anita K.; Lipton, Richard J.
1
1978
Polynomials that sign represent parity and Descartes’ rule of signs. Zbl 1188.68150
Basu, Saugata; Bhatnagar, Nayantara; Gopalan, Parikshit; Lipton, Richard J.
1
2008
Provably secure virus detection: using the observer effect against malware. Zbl 1388.68025
Lipton, Richard J.; Ostrovsky, Rafail; Zikas, Vassilis
1
2016
Provably-secure remote memory attestation for heap overflow protection. Zbl 1400.94123
Boldyreva, Alexandra; Kim, Taesoo; Lipton, Richard; Warinschi, Bogdan
1
2016
Quantum algorithms via linear algebra. A primer. Zbl 1315.68001
Lipton, Richard J.; Regan, Kenneth W.
2
2014
The \(\text{P}=\text{NP}\) question and Gödel’s lost letter. Zbl 1215.68101
Lipton, Richard J.
2
2010
On tractable exponential sums. Zbl 1288.68104
Cai, Jin-Yi; Chen, Xi; Lipton, Richard; Lu, Pinyan
2
2010
On the Fourier spectrum of symmetric Boolean functions. Zbl 1212.42017
Kolountzakis, Mihail N.; Lipton, Richard J.; Markakis, Evangelos; Mehta, Aranyak; Vishnoi, Nisheeth K.
7
2009
Deterministically testing sparse polynomial identities of unbounded degree. Zbl 1191.68822
Bläser, Markus; Hardt, Moritz; Lipton, Richard J.; Vishnoi, Nisheeth K.
3
2009
Best-order streaming model. Zbl 1241.68064
Das Sarma, Atish; Lipton, Richard J.; Nanongkai, Danupon
2
2009
Inapproximability results for combinatorial auctions with submodular utility functions. Zbl 1142.91485
Khot, Subhash; Lipton, Richard J.; Markakis, Evangelos; Mehta, Aranyak
14
2008
Algorithms for modular counting of roots of multivariate polynomials. Zbl 1143.11046
Gopalan, Parikshit; Guruswami, Venkatesan; Lipton, Richard J.
1
2008
Polynomials that sign represent parity and Descartes’ rule of signs. Zbl 1188.68150
Basu, Saugata; Bhatnagar, Nayantara; Gopalan, Parikshit; Lipton, Richard J.
1
2008
Intrusion-resilient key exchange in the bounded retrieval model. Zbl 1156.94338
Cash, David; Ding, Yan Zong; Dodis, Yevgeniy; Lee, Wenke; Lipton, Richard; Walfish, Shabsi
8
2007
Perfectly secure password protocols in the bounded retrieval model. Zbl 1112.68047
Di Crescenzo, Giovanni; Lipton, Richard; Walfish, Shabsi
12
2006
Symmetric polynomials over \(\mathbb Z_{m}\) and simultaneous communication protocols. Zbl 1094.68008
Bhatnagar, Nayantara; Gopalan, Parikshit; Lipton, Richard J.
3
2006
Time-space lower bounds for satisfiability. Zbl 1326.68148
Fortnow, Lance; Lipton, Richard; van Melkebeek, Dieter; Viglas, Anastasios
11
2005
Homogenization and design of functionally graded composites for stiffness and strength. Zbl 1320.74091
Lipton, R.
2
2005
Protecting secret data from insider attacks. Zbl 1120.94314
Dagon, David; Lee, Wenke; Lipton, Richard
1
2005
Estimating the maximum. Zbl 1090.62032
Gum, Ben; Lipton, Richard J.; LaPaugh, Andrea; Fich, Faith
1
2005
Nash equilibria via polynomial equations. Zbl 1196.91012
Lipton, Richard J.; Markakis, Evangelos
7
2004
On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\). Zbl 1044.68098
Karakostas, George; Lipton, Richard J.; Viglas, Anastasios
6
2003
Non-uniform depth of polynomial time and space simulations. Zbl 1278.68096
Lipton, Richard J.; Viglas, Anastasios
4
2003
Deterministic identity testing for multivariate polynomials. Zbl 1092.68724
Lipton, Richard; Vishnoi, Nisheeth
4
2003
On the importance of eliminating errors in cryptographic computations. Zbl 1018.94014
Boneh, Dan; DeMillo, Richard A.; Lipton, Richard J.
17
2001
The complexity of the \(A\) \(B\) \(C\) problem. Zbl 0967.20029
Cai, Jin-yi; Lipton, Richard J.; Zalcstein, Yechezkel
2
2000
Making DNA computers error resistant. Zbl 0919.68031
Boneh, Dan; Dunworth, Christopher; Lipton, Richard J.; Sgall, Jiří
10
1999
When the knight falls: On constructing an RNA computer. Zbl 0970.68059
Faulhammer, Dirk; Cukras, Anthony R.; Lipton, Richard J.; Landweber, Laura F.
1
1999
Reconstructing algebraic functions from mixed data. Zbl 0915.68088
Ar, Sigal; Lipton, Richard J.; Rubinfeld, Ronitt; Sudan, Madhu
7
1998
Algorithms for black-box fields and their application to cryptography. Zbl 1329.94053
Boneh, Dan; Lipton, Richard J.
21
1996
On the computational power of DNA. Zbl 0906.68071
Boneh, Dan; Dunworth, Christopher; Lipton, Richard J.; Sgall, Jiří
15
1996
Quantum cryptanalysis of hidden linear functions. (Extended abstract). Zbl 0876.94023
Boneh, Dan; Lipton, Richard J.
18
1995
Query size estimation by adaptive sampling. Zbl 0831.68035
Lipton, Richard J.; Naughton, Jeffrey F.
8
1995
Communication complexity of key agreement on small ranges. Zbl 1379.68127
Cai, Jin-Yi; Lipton, Richard J.; Longpré, Luc; Ogihara, Mitsunori; Regan, Kenneth W.; Sivakumar, D.
2
1995
Online interval scheduling. Zbl 0873.68012
Lipton, Richard J.; Tomkins, Andrew
33
1994
Cryptographic primitives based on hard learning problems. Zbl 0870.94021
Blum, Avrim; Furst, Merrick; Kearns, Michael; Lipton, Richard J.
29
1994
Simple strategies for large zero-sum games with applications to complexity theory. Zbl 1345.68175
Lipton, Richard J.; Young, Neal E.
14
1994
PSPACE is provable by two provers in one round. Zbl 0802.68055
Cai, Jin-yi; Condon, Anne; Lipton, Richard J.
7
1994
A new approach to information theory. Zbl 0941.94501
Lipton, Richard
5
1994
Straight-line complexity and integer factorization. Zbl 0842.11045
Lipton, Richard J.
4
1994
Subquadratic simulations of balanced formulae by branching programs. Zbl 0809.68068
Cai, Jin-Yi; Lipton, Richard J.
1
1994
A Monte-Carlo algorithm for estimating the permanent. Zbl 0781.05034
Karmarkar, N.; Karp, R.; Lipton, R.; Lovász, László; Luby, M.
26
1993
Efficient sampling strategies for relational database operations. Zbl 0797.68048
Lipton, Richard J.; Naughton, Jeffrey F.; Schneider, Donovan A.; Seshadri, S.
3
1993
Clocked adversaries for hashing. Zbl 0787.68028
Lipton, Richard J.; Naughton, Jeffrey F.
2
1993
On games of incomplete information. Zbl 0757.90090
Cai, Jin-yi; Condon, Anne; Lipton, Richard J.
4
1992
Reconsructing algebraic functions from mixed data. Zbl 0925.68221
Ar, Sigal; Lipton, Richard J.; Rubinfeld, Ronitt; Sudan, Madhu
3
1992
New directions in testing. Zbl 0722.68028
Lipton, Richard J.
14
1991
Set systems with no union of cardinality 0 modulo \(m\). Zbl 0762.05079
Alon, N.; Kleitman, D.; Lipton, R.; Meshulam, R.; Rabin, M.; Spencer, J.
6
1991
The processor identity problem. Zbl 0704.68007
Lipton, Richard J.; Park, Arvin
11
1990
Efficient checking of computations. Zbl 0729.68030
Lipton, Richard J.
11
1990
Playing games of incomplete information. Zbl 0786.90094
Cai, Jin-yi; Condon, Anne; Lipton, Richard J.
3
1990
Polynomial-time algorithm for the orbit problem. Zbl 1326.68162
Kannan, R.; Lipton, R. J.
18
1986
Unbounded fan-in circuits and associative functions. Zbl 0604.68051
Chandra, Ashok K.; Fortune, Steven; Lipton, Richard
17
1985
Pseudorandom number generation and space complexity. Zbl 0575.68048
Furst, Merrick; Lipton, Richard; Stockmeyer, Larry
1
1985
Alternating pushdown and stack automata. Zbl 0538.68039
Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J.
41
1984
Alternation bounded auxiliary pushdown automata. Zbl 0589.68058
Ladner, Richard E.; Stockmeyer, Larry J.; Lipton, Richard J.
6
1984
Lower bounds for constant depth circuits for prefix problems. Zbl 0536.68051
Chandra, Ashok K.; Fortune, Steven; Lipton, Richard
4
1983
Turing machines that take advice. Zbl 0529.68025
Karp, Richard M.; Lipton, Richard J.
57
1982
Turing machines that take advice. Zbl 0494.68061
Karp, Richard M.; Lipton, Richard J.
7
1982
On the structure of sets in NP and other complexity classes. Zbl 0482.68042
Landweber, L. H.; Lipton, R. J.; Robertson, E. L.
27
1981
Covering graphs by simple circuits. Zbl 0468.68071
Itai, Alon; Lipton, Richard J.; Papadimitriou, Christos H.; Rodeh, M.
20
1981
Computing extremal and approximate distances in graphs having unit cost edges. Zbl 0445.90090
Booth, Kellogg S.; Lipton, Richard J.
4
1981
Applications of a planar separator theorem. Zbl 0456.68077
Lipton, Richard J.; Tarjan, Robert Endre
139
1980
Addition chain methods for the evaluation of specific polynomials. Zbl 0447.68034
Dobkin, David; Lipton, Richard J.
4
1980
Social processes and proofs of theorems and programs. Zbl 0455.68017
DeMillo, Richard A.; Lipton, Richard J.; Perlis, Alan J.
4
1980
Space-time trade-offs in structured programming: An improved combinatorial embedding theorem. Zbl 0426.68046
DeMillo, Richard A.; Eisenstat, Stanley C.; Lipton, Richard J.
2
1980
External hashing schemes for collections of data structures. Zbl 0426.68051
Lipton, Richard J.; Rosenberg, Arnold L.; Yao, Andrew C.
2
1980
A separator theorem for planar graphs. Zbl 0432.05022
Lipton, Richard J.; Tarjan, Robert Endre
278
1979
Generalized nested dissection. Zbl 0435.65021
Lipton, Richard J.; Rose, Donald J.; Tarjan, Robert Endre
93
1979
On the complexity of computations under varying sets of primitives. Zbl 0409.68023
Dobkin, David P.; Lipton, Richard J.
28
1979
Linear programming is log-space hard for P. Zbl 0402.68042
Dobkin, David; Lipton, Richard J.; Reiss, Steven
23
1979
On the consistency of P=NP and fragments of arithmetic. Zbl 0419.03023
Lipton, Richard J.
1
1979
A constructive generalization of the Borel-Cantelli lemma with application to the complexity of infinite strings. Zbl 0434.03042
DeMillo, Richard A.; Lipton, Richard J.
1
1979
A probabilistic remark on algebraic program testing. Zbl 0397.68011
DeMillo, Richard A.; Lipton, Richard J.
78
1978
A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem. Zbl 0397.68045
Dobkin, David; Lipton, Richard J.
18
1978
Preserving average proximity in arrays. Zbl 0378.68014
DeMillo, Richard A.; Eisenstat, Stanley C.; Lipton, Richard J.
13
1978
A batching method for coloring planar graphs. Zbl 0395.05032
Lipton, Richard J.; Miller, Raymond E.
9
1978
Evaluation of polynomials with super-preconditioning. Zbl 0369.68031
Lipton, Richard J.; Stockmeyer, Larry J.
2
1978
Polynomials with 0-1 coefficients that are hard to evaluate. Zbl 0374.68039
Lipton, Richard J.
1
1978
The enforcement of security policies for computation. Zbl 0383.68034
Jones, Anita K.; Lipton, Richard J.
1
1978
Word problems solvable in logspace. Zbl 0359.68049
Lipton, Richard J.; Zalcstein, Yechezkel
41
1977
A separator theorem for planar graphs. Zbl 0417.05023
Lipton, Richard J.; Tarjan, Robert E.
10
1977
A linear time algorithm for deciding subject security. Zbl 0358.68041
Lipton, R. J.; Snyder, L.
10
1977
Synchronization and computing capabilities of linear asynchronous structures. Zbl 0368.02038
Lipton, R. J.; Miller, R. E.; Snyder, L.
5
1977
On the halting of tree replacement systems-premininary version. Zbl 0408.68046
Lipton, R. J.; Snyder, L.
4
1977
Aspects of the database security problem. Zbl 0456.68133
Dobkin, David; Lipton, Richard J.; Reiss, Steven P.
1
1977
Addition chain methods for the evaluation of specific polynomials. Zbl 0408.68042
Dobkin, David; Lipton, Richard
1
1977
Complexity measures and hierarchies for the evaluation of integers and polynomials. Zbl 0365.68049
Lipton, Richard J.; Dobkin, David
1
1977
Multidimensional searching problems. Zbl 0333.68031
Dobkin, David; Lipton, Richard J.
27
1976
Exponential space complete problems for Petri nets and commutative semigroups: Preliminary report. Zbl 0374.20067
Cardoza, E.; Lipton, R.; Meyer, A. R.
26
1976
Space and time hierarchies for classes of control structures and data structures. Zbl 0333.68024
Lipton, R. J.; Eisenstat, S. C.; DeMillo, R. A.
10
1976
A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem. Zbl 0362.68077
Dobkin, David; Lipton, Richard J.
3
1976
Reduction: A method of proving properties of parallel programs. Zbl 0316.68015
Lipton, Richard J.
31
1975
On the complexity of computations under varying sets of primitives. Zbl 0318.68034
Dobkin, David P.; Lipton, Richard J.
2
1975
The complexity of control structures and data structures. Zbl 0408.68037
Lipton, R. J.; Eisenstat, S. C.; DeMillo, R. A.
1
1975
Schedulers as enforces in synchronization processes. Zbl 0309.68058
Lipton, R. J.
3
1974
On some generalizations of binary search. Zbl 0361.68063
Dobkin, David; Lipton, R. J.
3
1974
Limitations of synchronization primitives with conditional branching and global variables. Zbl 0361.68093
Lipton, R. J.
3
1974
all top 5

Cited by 2,004 Authors

24 Pan, Victor Yakovlevich
15 Lipton, Richard J.
12 Reif, John H.
11 Williams, Richard Ryan
8 Bodlaender, Hans L.
8 Chan, Timothy Moon-Yew
8 Saxena, Nitin
8 Wigderson, Avi
8 Zehavi, Meirav
7 Fortnow, Lance J.
7 Fox, Jacob
7 Rosenberg, Arnold Leonard
6 Alon, Noga M.
6 Cai, Jin-Yi
6 Dvořák, Zdeněk
6 Geffert, Viliam
6 Har-Peled, Sariel
6 Lingas, Andrzej
6 Myasnikov, Alexei G.
6 Pach, János
6 Saurabh, Saket
6 Shparlinski, Igor E.
6 Shpilka, Amir
6 Teng, Shang-Hua
6 Thilikos, Dimitrios M.
6 Venturi, Daniele
5 Allender, Eric W.
5 Arvind, Vikraman
5 Bai, Fengshan
5 Birget, Jean-Camille
5 Björklund, Andreas
5 Downey, Rodney Graham
5 Faust, Sebastian
5 Fu, Bin
5 Gilbert, John R.
5 Jonsson, Peter A.
5 Klein, Philip N.
5 Liang, Heng
5 Lohrey, Markus
5 McKenzie, Pierre
5 Naor, Moni
5 Pietrzak, Krzysztof
5 Qian, Guoliang
5 Rubinfeld, Ronitt
5 Santhanam, Rahul
5 Schöning, Uwe
5 Vrto, Imrich
5 Watanabe, Osamu
5 Yamakami, Tomoyuki
4 Ambos-Spies, Klaus
4 Applebaum, Benny
4 Caro, Yair
4 Chazelle, Bernard
4 Clark, Peter Louis
4 Dobkin, David P.
4 Dragan, Feodor F.
4 Dujmović, Vida
4 Edelsbrunner, Herbert
4 Fomin, Fedor V.
4 Freivalds, Rūsiņš Mārtiņš
4 Galil, Zvi
4 Gurjar, Rohit
4 Hajiaghayi, Mohammad Taghi
4 Hemaspaandra, Lane A.
4 Howell, Rodney R.
4 Hromkovič, Juraj
4 Impagliazzo, Russell
4 Kabanets, Valentine
4 Linial, Nathan
4 Lokshtanov, Daniel
4 Mahajan, Meena
4 Mayr, Ernst W.
4 Meyer auf der Heide, Friedhelm
4 Mohar, Bojan
4 Naor, Joseph Seffi
4 Nisan, Noam
4 Ostrovsky, Rafail
4 Pardo, Luis Miguel
4 Potapov, Igor
4 Rote, Günter
4 Spirakis, Paul G.
4 Thierauf, Thomas
4 Vaikuntanathan, Vinod
4 van Melkebeek, Dieter
4 Vitter, Jeffrey Scott
4 Wood, David Ronald
4 Wood, Derick
4 Yan, Chenyu
4 Yan, Xiaodong
3 Agrawal, Manindra
3 Aizikowitz, Tamar
3 Aspnes, James
3 Baïou, Mourad
3 Barahona, Francisco
3 Bell, Paul C.
3 Berend, Daniel
3 Bhattacharyya, Arnab
3 Biha, Mohamed Didi
3 Blum, Manuel
3 Boneh, Dan
...and 1,904 more Authors
all top 5

Cited in 195 Serials

165 Theoretical Computer Science
86 Journal of Computer and System Sciences
69 Information Processing Letters
61 Algorithmica
40 Information and Computation
32 Discrete Applied Mathematics
30 Computational Complexity
22 Theory of Computing Systems
20 SIAM Journal on Computing
20 Discrete & Computational Geometry
17 Computational Geometry
16 Acta Informatica
16 Discrete Mathematics
16 Linear Algebra and its Applications
15 Mathematical Systems Theory
14 Combinatorica
14 Journal of Symbolic Computation
14 Journal of Cryptology
13 Computers & Mathematics with Applications
13 Journal of Combinatorial Theory. Series B
13 SIAM Journal on Discrete Mathematics
11 Computing
11 Journal of Combinatorial Optimization
10 Mathematical Programming. Series A. Series B
9 Annals of Pure and Applied Logic
9 International Journal of Foundations of Computer Science
8 European Journal of Combinatorics
8 Operations Research Letters
8 Journal of Complexity
8 Designs, Codes and Cryptography
8 Distributed Computing
7 Applied Mathematics and Computation
7 International Journal of Computer Mathematics
7 RAIRO. Informatique Théorique et Applications
6 Journal of Algebra
5 Israel Journal of Mathematics
5 Advances in Mathematics
5 BIT
5 Information Sciences
5 Numerische Mathematik
5 SIAM Journal on Algebraic and Discrete Methods
5 Computers & Operations Research
5 Random Structures & Algorithms
5 International Journal of Algebra and Computation
5 European Journal of Operational Research
5 Combinatorics, Probability and Computing
5 Journal of Discrete Algorithms
4 Artificial Intelligence
4 Graphs and Combinatorics
4 Formal Aspects of Computing
4 International Journal of Computational Geometry & Applications
4 Journal of Global Optimization
4 Applicable Algebra in Engineering, Communication and Computing
4 Cybernetics and Systems Analysis
4 Formal Methods in System Design
4 SIAM Journal on Scientific Computing
4 RAIRO. Theoretical Informatics and Applications
3 Journal of Computational and Applied Mathematics
3 Transactions of the American Mathematical Society
3 Cybernetics
3 Journal of Automated Reasoning
3 SIAM Journal on Matrix Analysis and Applications
3 Games and Economic Behavior
3 Computational Optimization and Applications
3 The Electronic Journal of Combinatorics
3 Annals of Mathematics and Artificial Intelligence
3 Parallel Algorithms and Applications
3 Journal of the ACM
3 Discrete Optimization
3 Optimization Letters
3 Cryptography and Communications
2 Communications in Mathematical Physics
2 Computer Methods in Applied Mechanics and Engineering
2 Fluid Dynamics
2 Journal of Computational Physics
2 Automatica
2 International Journal of Computer & Information Sciences
2 Journal of Combinatorial Theory. Series A
2 Journal of Graph Theory
2 Journal of Pure and Applied Algebra
2 Journal of Soviet Mathematics
2 RAIRO, Informatique Théorique
2 Semigroup Forum
2 Advances in Applied Mathematics
2 Mathematical Social Sciences
2 Journal of Computer Science and Technology
2 New Generation Computing
2 Journal of the American Mathematical Society
2 Annals of Operations Research
2 MSCS. Mathematical Structures in Computer Science
2 Geometric and Functional Analysis. GAFA
2 Computational Statistics and Data Analysis
2 Journal of Mathematical Sciences (New York)
2 Finite Fields and their Applications
2 Discussiones Mathematicae. Graph Theory
2 Journal of Scheduling
2 Journal of Graph Algorithms and Applications
2 Journal of Integer Sequences
2 Sādhanā
2 Multiscale Modeling & Simulation
...and 95 more Serials
all top 5

Cited in 46 Fields

883 Computer science (68-XX)
294 Combinatorics (05-XX)
145 Information and communication theory, circuits (94-XX)
142 Operations research, mathematical programming (90-XX)
107 Numerical analysis (65-XX)
82 Mathematical logic and foundations (03-XX)
50 Number theory (11-XX)
45 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
43 Group theory and generalizations (20-XX)
36 Linear and multilinear algebra; matrix theory (15-XX)
34 Convex and discrete geometry (52-XX)
24 Quantum theory (81-XX)
22 Field theory and polynomials (12-XX)
20 Algebraic geometry (14-XX)
17 Biology and other natural sciences (92-XX)
15 Probability theory and stochastic processes (60-XX)
12 Commutative algebra (13-XX)
12 Statistics (62-XX)
10 Order, lattices, ordered algebraic structures (06-XX)
9 Geometry (51-XX)
7 Systems theory; control (93-XX)
6 Partial differential equations (35-XX)
6 Dynamical systems and ergodic theory (37-XX)
6 Manifolds and cell complexes (57-XX)
5 Associative rings and algebras (16-XX)
4 Real functions (26-XX)
4 Mechanics of deformable solids (74-XX)
3 History and biography (01-XX)
3 General algebraic systems (08-XX)
3 Difference and functional equations (39-XX)
3 Differential geometry (53-XX)
2 General and overarching topics; collections (00-XX)
2 Functions of a complex variable (30-XX)
2 Harmonic analysis on Euclidean spaces (42-XX)
2 Abstract harmonic analysis (43-XX)
2 Operator theory (47-XX)
2 Global analysis, analysis on manifolds (58-XX)
2 Fluid mechanics (76-XX)
2 Statistical mechanics, structure of matter (82-XX)
1 Category theory; homological algebra (18-XX)
1 Measure and integration (28-XX)
1 Special functions (33-XX)
1 Sequences, series, summability (40-XX)
1 Functional analysis (46-XX)
1 General topology (54-XX)
1 Mechanics of particles and systems (70-XX)

Citations by Year