Edit Profile (opens in new tab) Joseph, Deborah Co-Author Distance Author ID: joseph.deborah Published as: Joseph, Deborah; Joseph, D. Documents Indexed: 25 Publications since 1981 1 Further Contribution Co-Authors: 13 Co-Authors with 17 Joint Publications 550 Co-Co-Authors all top 5 Co-Authors 1 single-authored 5 Das, Gautam 4 Goldsmith, Judy 3 Bruschi, Danilo 3 Dobkin, David P. 2 Althöfer, Ingo 2 Hopcroft, John Edward H. 2 Sitharam, Meera 2 Whitesides, Sue H. 1 Angluin, Dana 1 Bertoni, Alberto 1 Bloniarz, Peter A. 1 Borodin, Allan B. 1 Brent, Richard Peirce 1 Brown, Donna J. 1 Carlson, David A. 1 Chazelle, Bernard 1 Cook, Stephen Arthur 1 Cypher, A. 1 DeMillo, Richard Allan 1 Duhan, S. 1 Ehrig, Hartmut 1 Fagin, Ronald 1 Filotti, I. S. 1 Fischer, Michael J. 1 Frederickson, Greg N. 1 Guibas, Leonidas John 1 Harrison, Andrew P. 1 Heintz, Joos 1 Hemaspaandra, Lane A. 1 Hoffmann, Christoph M. 1 Hong, Jiawei 1 Ibarra, Oscar H. 1 Ja’Ja’, Joseph F. 1 Johnson, Donald B. 1 Kannan, Ravindran 1 Karp, Richard Manning 1 Kung, H. T. 1 Leininger, Brian S. 1 Lichtenstein, David 1 Lipton, Richard Jay 1 Lloyd, Errol L. 1 Lynch, Nancy Ann 1 Mahr, Bernd 1 Mayer, Jack N. 1 Meidanis, João 1 Meyer, Albert Ronald 1 Miller, Gary Lee 1 Miller, Raymond E. 1 Mirkowska, Grazyna 1 Overmars, Mark H. 1 Parikh, Rohit 1 Paterson, Mike S. 1 Paul, Wolfgang Jakob 1 Pippenger, Nicholas J. 1 Plaisted, David Alan 1 Pratt, Vaughan R. 1 Reif, John H. 1 Reingold, Edward Martin 1 Sadri, Fereidoon 1 Savage, John E. 1 Schnorr, Claus Peter 1 Seiferas, Joel I. 1 Simon, Janos 1 Soares, Jose F. 1 Spirakis, Paul G. 1 Storer, James A. 1 Strong, H. Raymond 1 Supowit, Kenneth J. 1 Tarjan, Robert Endre 1 Tiwari, Prasoon 1 Tompa, Martin 1 Toueg, Sam 1 Ukkonen, Esko 1 Ullman, Jeffrey David 1 Van Leeuwen, Jan 1 Yao, Frances F. 1 Yap, Chee-Keng all top 5 Serials 4 Journal of Computer and System Sciences 3 SIAM Journal on Computing 2 Theoretical Computer Science 1 International Journal of Modern Physics B 1 Annales Societatis Mathematicae Polonae. Series IV 1 Discrete & Computational Geometry 1 Information and Computation 1 Bulletin of the European Association for Theoretical Computer Science (EATCS) 1 International Journal of Foundations of Computer Science 1 Computational Complexity 1 SIAM Journal on Scientific Computing all top 5 Fields 22 Computer science (68-XX) 9 Mathematical logic and foundations (03-XX) 4 Combinatorics (05-XX) 1 General and overarching topics; collections (00-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Numerical analysis (65-XX) 1 Mechanics of particles and systems (70-XX) 1 Optics, electromagnetic theory (78-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Biology and other natural sciences (92-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 19 Publications have been cited 380 times in 355 Documents Cited by ▼ Year ▼ On sparse spanners of weighted graphs. Zbl 0762.05039 Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah; Soares, José 218 1993 Some remarks on witness functions for nonpolynomial and noncomplete sets in NP. Zbl 0597.68042 Joseph, Deborah; Young, Paul 40 1985 Which triangulations approximate the complete graph? Zbl 0704.68087 Das, G.; Joseph, D. 27 1989 Movement problems for 2-dimensional linkages. Zbl 0588.68054 Hopcroft, John; Joseph, Deborah; Whitesides, Sue 15 1984 Determining DNA sequence similarity using maximum independent set algorithms for interval graphs. Zbl 1502.92009 Joseph, Deborah; Meidanis, Joao; Tiwari, Prasoon 13 1992 On the movement of robot arms in 2-dimensional bounded regions. Zbl 0597.68040 Hopcroft, John; Joseph, Deborah; Whitesides, Sue 12 1985 Independence results in computer science? Zbl 0474.68046 Joseph, Deborah; Young, Paul 7 1981 Generalized Boolean hierarchies and Boolean hierarchies over RP. Zbl 0756.68037 Bertoni, Alberto; Bruschi, Danilo; Joseph, Deborah; Sitharam, Meera; Young, Paul 7 1989 Near-testable sets. Zbl 0738.68031 Goldsmith, Judy; Hemachandra, Lane A.; Joseph, Deborah; Young, Paul 7 1991 Generating sparse spanners for weighted graphs. Zbl 1502.68198 Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah 7 1990 A structural overview of NP optimization problems. Zbl 0704.68004 Bruschi, D.; Joseph, D.; Young, P. 5 1989 Strong separations for the Boolean hierarchy over RP. Zbl 0732.68039 Bruschi, Danilo; Joseph, Deborah; Young, Paul 5 1990 A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly. Zbl 0771.68051 Goldsmith, Judy; Joseph, Deborah; Young, Paul 4 1993 Using self-reducibilities to characterize polynomial time. Zbl 0776.68044 Goldsmith, Judy; Joseph, Deborah; Young, Paul 3 1993 Relativized isomorphisms of NP-complete sets. Zbl 0801.68065 Goldsmith, Judy; Joseph, Deborah 3 1993 Minimum vertex hulls for polyhedral domains. Zbl 0753.68091 Das, Gautam; Joseph, Deborah 3 1992 A survey of some recent results on computational complexity in weak theories of arithmetic. Zbl 0606.03016 Joseph, Deborah; Young, Paul 2 1985 Kolmogorov complexity, restricted nondeterminism and generalized spectra. Zbl 0731.03024 Joseph, Deborah; Sitharam, Meera 1 1990 Polynomial time computations in models of ET. Zbl 0542.03019 Joseph, Deborah 1 1983 On sparse spanners of weighted graphs. Zbl 0762.05039 Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah; Soares, José 218 1993 A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly. Zbl 0771.68051 Goldsmith, Judy; Joseph, Deborah; Young, Paul 4 1993 Using self-reducibilities to characterize polynomial time. Zbl 0776.68044 Goldsmith, Judy; Joseph, Deborah; Young, Paul 3 1993 Relativized isomorphisms of NP-complete sets. Zbl 0801.68065 Goldsmith, Judy; Joseph, Deborah 3 1993 Determining DNA sequence similarity using maximum independent set algorithms for interval graphs. Zbl 1502.92009 Joseph, Deborah; Meidanis, Joao; Tiwari, Prasoon 13 1992 Minimum vertex hulls for polyhedral domains. Zbl 0753.68091 Das, Gautam; Joseph, Deborah 3 1992 Near-testable sets. Zbl 0738.68031 Goldsmith, Judy; Hemachandra, Lane A.; Joseph, Deborah; Young, Paul 7 1991 Generating sparse spanners for weighted graphs. Zbl 1502.68198 Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah 7 1990 Strong separations for the Boolean hierarchy over RP. Zbl 0732.68039 Bruschi, Danilo; Joseph, Deborah; Young, Paul 5 1990 Kolmogorov complexity, restricted nondeterminism and generalized spectra. Zbl 0731.03024 Joseph, Deborah; Sitharam, Meera 1 1990 Which triangulations approximate the complete graph? Zbl 0704.68087 Das, G.; Joseph, D. 27 1989 Generalized Boolean hierarchies and Boolean hierarchies over RP. Zbl 0756.68037 Bertoni, Alberto; Bruschi, Danilo; Joseph, Deborah; Sitharam, Meera; Young, Paul 7 1989 A structural overview of NP optimization problems. Zbl 0704.68004 Bruschi, D.; Joseph, D.; Young, P. 5 1989 Some remarks on witness functions for nonpolynomial and noncomplete sets in NP. Zbl 0597.68042 Joseph, Deborah; Young, Paul 40 1985 On the movement of robot arms in 2-dimensional bounded regions. Zbl 0597.68040 Hopcroft, John; Joseph, Deborah; Whitesides, Sue 12 1985 A survey of some recent results on computational complexity in weak theories of arithmetic. Zbl 0606.03016 Joseph, Deborah; Young, Paul 2 1985 Movement problems for 2-dimensional linkages. Zbl 0588.68054 Hopcroft, John; Joseph, Deborah; Whitesides, Sue 15 1984 Polynomial time computations in models of ET. Zbl 0542.03019 Joseph, Deborah 1 1983 Independence results in computer science? Zbl 0474.68046 Joseph, Deborah; Young, Paul 7 1981 all cited Publications top 5 cited Publications all top 5 Cited by 586 Authors 17 Hemaspaandra, Lane A. 10 Dumitrescu, Adrian 9 Bose, Prosenjit K. 9 Neiman, Ofer 9 Tóth, Csaba D. 7 Elkin, Michael 7 Filtser, Arnold 6 Dragan, Feodor F. 6 Ghosh, Anirban 6 Smid, Michiel H. M. 5 Joseph, Deborah 5 Solomon, Shay 5 van Renssen, André 4 Abam, Mohammad Ali 4 Allender, Eric W. 4 Beigel, Richard 4 Carmi, Paz 4 Das, Gautam 4 Dinitz, Michael H. 4 Eppstein, David Arthur 4 Gudmundsson, Joachim 4 Hoene, Albrecht 4 Kavitha, Telikepalli 4 Lam, Kam-Yiu 4 Levcopoulos, Christos 4 Peleg, David 3 Agrawal, Manindra 3 Ahmed, Reyan 3 Alstrup, Stephen 3 Ausiello, Giorgio 3 Bilò, Davide 3 Bodwin, Greg 3 Cai, Jin-Yi 3 Chen, Ke 3 Church, Richard L. 3 Du, Ding-Zhu 3 Farshi, Mohammad 3 Franciosa, Paolo Giulio 3 Golovach, Petr A. 3 Gualà, Luciano 3 Gupta, Anupam 3 Hamm, Keaton 3 Italiano, Giuseppe Francesco 3 Kawarabayashi, Ken-ichi 3 Kobourov, Stephen G. 3 Leucci, Stefano 3 Liestman, Arthur L. 3 Lovett, Shachar 3 Maheshwari, Anil 3 Meka, Raghu 3 Morin, Pat 3 Mulzer, Wolfgang Johann Heinrich 3 Ogihara, Mitsunori 3 Panconesi, Alessandro 3 Pettie, Seth 3 Proietti, Guido 3 Roditty, Liam 3 Rothe, Jörg-Matthias 3 Shermer, Thomas Caton 3 Spence, Richard 3 Thorup, Mikkel 3 Ueckerdt, Torsten 3 Whitesides, Sue H. 3 Yan, Chenyu 3 Zhu, Chun Jiang 3 Zimand, Marius 3 Zwick, Uri 2 Abboud, Amir 2 Abraham, Ittai 2 Aggarwal, Divesh 2 Ahn, Jungho 2 Aichholzer, Oswin 2 Akhoondian Amiri, Saeed 2 Althöfer, Ingo 2 Ambainis, Andris 2 Andoni, Alexandr 2 Aurenhammer, Franz 2 Bačkurs, Artūrs 2 Bansal, Nikhil 2 Barak, Boaz 2 Bartal, Yair 2 Bernstein, Aaron 2 Bhore, Sujoy Kumar 2 Biswas, Somenath 2 Braverman, Mark 2 Chang, Richard 2 Chaplick, Steven 2 Chechik, Shiri 2 Chen, Xi 2 Chlamtac, Eden 2 Cohen, Michael B. 2 Czumaj, Artur 2 Daescu, Ovidiu 2 Dahlgaard, Søren 2 Däubel, Karl 2 de Carufel, Jean-Lou 2 Disser, Yann 2 Dobkin, David P. 2 Feldman, Vitaly 2 Fertin, Guillaume ...and 486 more Authors all top 5 Cited in 40 Serials 47 Theoretical Computer Science 20 Algorithmica 16 Journal of Computer and System Sciences 14 Computational Geometry 11 Information Processing Letters 10 Mathematical Systems Theory 8 SIAM Journal on Computing 8 Discrete & Computational Geometry 7 Discrete Applied Mathematics 5 Discrete Mathematics 5 Information and Computation 5 SIAM Journal on Discrete Mathematics 5 International Journal of Computational Geometry & Applications 4 Theory of Computing Systems 4 Journal of Discrete Algorithms 3 Artificial Intelligence 3 European Journal of Operational Research 3 Distributed Computing 2 Networks 2 Computers & Operations Research 2 International Journal of Foundations of Computer Science 2 Computational Complexity 2 RAIRO. Theoretical Informatics and Applications 2 Discrete Mathematics, Algorithms and Applications 2 Computer Science Review 1 Acta Informatica 1 Journal of Soviet Mathematics 1 Combinatorica 1 Acta Mathematicae Applicatae Sinica. English Series 1 Journal of Complexity 1 Journal of Computer Science and Technology 1 Mathematical Logic Quarterly (MLQ) 1 Journal of Automata, Languages and Combinatorics 1 Journal of Combinatorial Optimization 1 Sibirskiĭ Zhurnal Industrial’noĭ Matematiki 1 Optimization Letters 1 S\(\vec{\text{e}}\)MA Journal 1 Mathematical Sciences 1 Computational and Mathematical Biophysics 1 CGT. Computing in Geometry and Topology all top 5 Cited in 26 Fields 310 Computer science (68-XX) 112 Combinatorics (05-XX) 30 Mathematical logic and foundations (03-XX) 26 Operations research, mathematical programming (90-XX) 24 Information and communication theory, circuits (94-XX) 12 Convex and discrete geometry (52-XX) 11 Numerical analysis (65-XX) 11 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 5 Mechanics of particles and systems (70-XX) 4 Quantum theory (81-XX) 3 Geometry (51-XX) 3 Systems theory; control (93-XX) 2 Group theory and generalizations (20-XX) 2 Functional analysis (46-XX) 2 General topology (54-XX) 2 Statistics (62-XX) 2 Biology and other natural sciences (92-XX) 1 History and biography (01-XX) 1 Number theory (11-XX) 1 Commutative algebra (13-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Measure and integration (28-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Algebraic topology (55-XX) 1 Probability theory and stochastic processes (60-XX) 1 Statistical mechanics, structure of matter (82-XX) Citations by Year