# Deborah Joseph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Deborah_Joseph
> Markdown URL: https://mediated.wiki/source/Deborah_Joseph.md
> Source: https://en.wikipedia.org/wiki/Deborah_Joseph
> Source revision: 1329515447
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

For the British journalist and editor, see [Deborah Joseph (editor)](/source/Deborah_Joseph_(editor)).

**Deborah A. Joseph** is an American computer scientist known for her research in [computational geometry](/source/Computational_geometry), [computational biology](/source/Computational_biology), and [computational complexity theory](/source/Computational_complexity_theory). She is a professor emeritus of computer science at the [University of Wisconsin–Madison](/source/University_of_Wisconsin%E2%80%93Madison).[1]

## Education and career

Joseph graduated from [Hiram College](/source/Hiram_College) in 1976 with an interdisciplinary major in [ecology](/source/Ecology).[2] She earned her Ph.D. in 1981 at [Purdue University](/source/Purdue_University). Her dissertation, *On the Power of Formal Systems for Analyzing Linear and Polynomial Time Program Behavior*, was supervised by Paul R. Young.[3]

At Wisconsin, Joseph was a recipient of the [Presidential Young Investigator Award](/source/Presidential_Young_Investigator_Award) of the [National Science Foundation](/source/National_Science_Foundation). She was also an active member of the Computer Science and Telecommunications Board of the [National Research Council](/source/National_Research_Council_(United_States)).[2]

## Selected publications

- Joseph, Deborah & Young, Paul (1985), ["Some remarks on witness functions for nonpolynomial and noncomplete sets in NP"](https://digital.library.wisc.edu/1793/58504), *[Theoretical Computer Science](/source/Theoretical_Computer_Science_(journal))*. **39** (2–3): 225–237, [doi:10.1016/0304-3975(85)90140-9](https://doi.org/10.1016/0304-3975(85)90140-9). MR 821203. This paper introduces the [k-creative sets](/source/Polynomial_creativity), which form a potential counterexample to the [Berman–Hartmanis conjecture](/source/Berman%E2%80%93Hartmanis_conjecture).
- Hopcroft, John; Joseph, Deborah; Whitesides, Sue (1985), "On the movement of robot arms in 2-dimensional bounded regions", *[SIAM Journal on Computing](/source/SIAM_Journal_on_Computing)*. **14** (2): 315–333, [doi:10.1137/0214025](https://doi.org/10.1137/0214025). MR 784740. [S2CID 16477060](https://api.semanticscholar.org/CorpusID:16477060). Expanded version of a paper from the 23rd [Symposium on Foundations of Computer Science](/source/Symposium_on_Foundations_of_Computer_Science) (FOCS 1982).
- Joseph, Deborah; Meidânis, João; Tiwari, Prasoon (1992), "Determining DNA sequence similarity using maximum independent set algorithms for interval graphs", *Algorithm Theory — SWAT '92: Third Scandinavian Workshop on Algorithm Theory, Helsinki, Finland, July 8–10, 1992, Proceedings*, Vol. 621, Lecture Notes in Computer Science, Berlin: Springer, pp. 326–337, [doi:10.1007/3-540-55706-7_29](https://doi.org/10.1007/3-540-55706-7_29). ISBN 978-3-540-55706-7. MR 1249510.
- Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah; Soares, José (1993), "On sparse spanners of weighted graphs", *[Discrete & Computational Geometry](/source/Discrete_%26_Computational_Geometry)*. **9** (1): 81–100, [doi:10.1007/BF02189308](https://doi.org/10.1007/BF02189308). MR 1184695. Expanded version of a paper from the 2nd [Scandinavian Workshop on Algorithm Theory](/source/Scandinavian_Workshop_on_Algorithm_Theory) (SWAT 1990) and the PhD thesis[4] of Joseph's student [Gautam Das](/source/Gautam_Das_(computer_scientist)), in which they discover [greedy geometric spanners](/source/Greedy_geometric_spanner).

## References

1. ["Deborah Joseph, Emeritus Professor"](https://www.cs.wisc.edu/people/joseph), [University of Wisconsin–Madison](/source/University_of_Wisconsin%E2%80%93Madison), retrieved 2018-12-09

1. National Research Council Computer Science and Telecommunications Board (1997), [*Defining a Decade: Envisioning CSTB's Second 10 Years*](https://books.google.com/books?id=RI0rAAAAYAAJ&pg=PA99), National Academies Press, p. 99, ISBN 9780309059336

1. Das, Gautam. *Approximation schemes in computational geometry*. [OCLC 22935858](https://www.worldcat.org/oclc/22935858)

---
Adapted from the Wikipedia article [Deborah Joseph](https://en.wikipedia.org/wiki/Deborah_Joseph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Deborah_Joseph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.