Deborah Joseph

Computer Science · Physical Sciences

16h-index1.4kcitations38works0.02yr avg
OpenAlex↗Google Scholar↗

Accepting Students?

No reports yet. Know if this professor is taking students?

Research Topics

Computability, Logic, AI Algorithms(13), Complexity and Algorithms in Graphs(10), semigroups and automata theory(7), Advanced Graph Theory Research(5), Computational Geometry and Mesh Generation(5)

Publications38 total

Which triangulations approximate the complete graph?
Lecture notes in computer science·1989· 97 cited
A structural overview of NP optimization problems
Lecture notes in computer science·1989· 21 cited
Generalized Boolean hierarchies and Boolean hierarchies over RP
Lecture notes in computer science·1989· 25 cited
The Structural Complexity Column, guest authors.
Bulletin of the European Association for Theoretical Computer Science·1988· 1 cited
Self-Reducible, P-Selective, Near-Testable, and P-Cheatable Sets: The Effect of Internal Structure on the Complexity of a Set
1987· 19 cited
Near-testable, P-cheatable, and P-terse sets.
Structure in Complexity Theory Annual Conference·1987
Three results on the polynomial isomorphism of complete sets
1986· 32 cited
On the Movement of Robot Arms in 2-Dimensional Bounded Regions
SIAM Journal on Computing·1985· 67 cited
Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
Theoretical Computer Science·1985· 117 cited
Movement Problems for 2-Dimensional Linkages
SIAM Journal on Computing·1984· 103 cited
Polynomial time computations in models of ET
Journal of Computer and System Sciences·1983· 5 cited
On the movement of robot arms in 2-dimensional bounded regions
1982· 26 cited
Corrigendum
Journal of Computer and System Sciences·1982· 1 cited
Corrigendum: Independence Results in Computer Science?
Journal of Computer and System Sciences·1982· 1 cited
Independence results in computer science?
Journal of Computer and System Sciences·1981· 23 cited
A survey of some recent results on computational complexity in weak theories of arithmetic
Lecture notes in computer science·1981· 9 cited
Fast programs for initial segments and polynomial time computation in weak models of arithmetic (Preliminary Abstract)
1981· 3 citedOpen Access
Independence results in Computer Science? (Preliminary Version)
1980· 5 cited
← Previouspage 2 of 2

Frequent Co-authors

Paul R. Young(13), Judy Goldsmith(7), Gautam Das(5), John E. Hopcroft(3), Sue Whitesides(3), Ingo Althöfer(2), David Dobkin(2), João Meidânis(2), Meera Sitharam(2), Danilo Bruschi(2), Paul Young(2), José Soares(1), Prasoon Tiwari(1), Alberto Bertoni(1), Danilo Bruschi(1), Lane A. Hemachandra(1), Paul Young(1), W. Istvanick(1), A. Kryder(1), Gary Lewandowski(1)