Deborah Joseph

Deborah A. Joseph är en amerikansk datavetare känd för sin forskning inom beräkningsgeometri , beräkningsbiologi och beräkningskomplexitetsteori . Hon är professor emeritus i datavetenskap vid University of Wisconsin–Madison .

Utbildning och karriär

Joseph tog examen från Hiram College 1976 med en tvärvetenskaplig huvudämne i ekologi . Hon tog sin doktorsexamen. 1981 vid Purdue University . Hennes avhandling, On the Power of Formal Systems for Analyzing Linear and Polynomial Time Program Behavior, handledes av Paul R. Young.

I Wisconsin var Joseph mottagare av Presidential Young Investigator Award från National Science Foundation . Hon var också en aktiv ledamot av Datavetenskap och telekommunikationsstyrelsen i National Research Council .

Utvalda publikationer

Josef, Debora; Young, Paul (1985), "Some remarks on witness functions for nonpolynomial and noncomplete sets in NP", Theoretical Computer Science , 39 (2–3): 225–237, doi : 10.1016/0304-3975(85)90140-9 MR 0821203 . _ Denna artikel introducerar $k$ -kreativa uppsättningar , som utgör ett potentiellt motexempel till Berman-Hartmanis-förmodan .
Hopcroft, John ; Josef, Debora; Whitesides, Sue ( 1985), "On the movement of robot arms in 2-dimensional bounded regions", SIAM Journal on Computing , 14 (2): 315–333, doi : 10.1137/0214025 , MR 0784740 , S2770606 . Utökad version av en artikel från det 23:e symposiet om grunder för datavetenskap ( FOCS 1982).
Josef, Debora; 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, Helsingfors, Finland, 8–10 juli 1992, Proceedings , Lecture Notes in Computer Science, vol. 621, Berlin: Springer, s. 326–337, doi : 10.1007/3-540-55706-7_29 , MR 1249510 .
Althöfer, Ingo ; Das, Gautam ; Dobkin, David ; Josef, Debora; Soares, José (1993), "On sparse spanners of weighted graphs", Discrete & Computational Geometry , 9 (1): 81–100, doi : 10.1007/BF02189308 , MR 1184695 . Utökad version av en artikel från 2nd Scandinavian Workshop on Algorithm Theory (SWAT 1990) och doktorsavhandlingen av Josephs student Gautam Das , där de upptäcker giriga geometriska skiftnycklar .