Deborah A. Joseph is an American computer scientist known for her research in computational geometry, computational biology, and

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

. She is a professor emeritus of computer science at the

University of Wisconsin–Madison A university () is an institution of higher (or tertiary) education and research which awards academic degrees in several academic disciplines. Universities typically offer both undergraduate and postgraduate programs. In the United Stat ...

Education and career

Joseph graduated from

Hiram College Hiram College ( ) is a private liberal arts college in Hiram, Ohio. It was founded in 1850 as the Western Reserve Eclectic Institute by Amos Sutton Hayden and other members of the Disciples of Christ Church. The college is nonsectarian and c ...

in 1976 with an interdisciplinary major in

ecology Ecology () is the study of the relationships between living organisms, including humans, and their physical environment. Ecology considers organisms at the individual, population, community, ecosystem, and biosphere level. Ecology overl ...

. She earned her Ph.D. in 1981 at

Purdue University Purdue University is a public land-grant research university in West Lafayette, Indiana, and the flagship campus of the Purdue University system. The university was founded in 1869 after Lafayette businessman John Purdue donated land and mone ...

. Her dissertation, ''On the Power of Formal Systems for Analyzing Linear and Polynomial Time Program Behavior'', was supervised by Paul R. Young. At Wisconsin, Joseph was a recipient of the

Presidential Young Investigator Award The Presidential Young Investigator Award (PYI) was awarded by the National Science Foundation of the United States Federal Government. The program operated from 1984 to 1991, and was replaced by the NSF Young Investigator (NYI) Awards and Presiden ...

of the

National Science Foundation The National Science Foundation (NSF) is an independent agency of the United States government that supports fundamental research and education in all the non-medical fields of science and engineering. Its medical counterpart is the National ...

. She was also an active member of the Computer Science and Telecommunications Board of the

National Research Council National Research Council may refer to: * National Research Council (Canada), sponsoring research and development * National Research Council (Italy), scientific and technological research, Rome * National Research Council (United States), part of ...

Selected publications

*. This paper introduces the -creative sets, which form a potential counterexample to the

Berman–Hartmanis conjecture In structural complexity theory, the Berman–Hartmanis conjecture is an unsolved conjecture named after Leonard C. Berman and Juris Hartmanis that states that all NP-complete languages look alike, in the sense that they can be related to each ot ...

. *. Expanded version of a paper from the 23rd Symposium on Foundations of Computer Science (FOCS 1982). *. *. Expanded version of a paper from the 2nd Scandinavian Workshop on Algorithm Theory (SWAT 1990) and the PhD thesis of Joseph's student Gautam Das, in which they discover greedy geometric spanners.

References

{{DEFAULTSORT:Joseph, Deborah Year of birth missing (living people) Living people American computer scientists American women computer scientists Hiram College alumni Purdue University alumni University of Wisconsin–Madison faculty Researchers in geometric algorithms American women academics 21st-century American women