David Karger

David Karger
Född
David Ron Karger

( 1967-05-01 ) 1 maj 1967 (55 år)
Alma mater
Harvard University Stanford University
Känd för

Kargers algoritm Chord (peer-to-peer) Konsekvent hashning
Make Allegra Goodman
Utmärkelser ACM-stipendiat
Vetenskaplig karriär
Fält


Informationshantering Människa-datorinteraktion Semantisk webb- PIM
institutioner


Harvard University Stanford University MIT Xerox PARC
Avhandling   Slumpmässigt urval i grafoptimeringsproblem (1995)
Doktorandrådgivare Rajeev Motwani
Doktorander
Hemsida människor .csail .mit .edu /karger

David Ron Karger (född 1 maj 1967) är professor i datavetenskap och medlem av Computer Science and Artificial Intelligence Laboratory ( CSAIL ) vid Massachusetts Institute of Technology .

Utbildning

Karger fick en Bachelor of Arts -examen från Harvard University och en doktorsexamen i datavetenskap från Stanford University .

Forskning

Kargers arbete med algoritmer har fokuserat på tillämpningar av randomisering till optimeringsproblem och lett till betydande framsteg på flera kärnproblem. Han är ansvarig för Kargers algoritm , en Monte Carlo-metod för att beräkna minimisnittet för en sammankopplad graf. Karger utvecklade den snabbaste för minimum spaning tree hittills, med Philip Klein och Robert Tarjan . De hittade en linjär tidsrandomiserad algoritm baserad på en kombination av Borůvkas algoritm och omvänd-delete-algoritmen. Tillsammans med Ion Stoica , Robert Morris , Frans Kaashoek och Hari Balakrishnan utvecklade han också Chord , ett av de fyra ursprungliga distribuerade hashtabellsprotokollen .

Karger har bedrivit forskning inom området informationssökning och personlig informationshantering . Detta arbete har fokuserat på nya gränssnitt och algoritmer för att hjälpa människor att effektivt sålla igenom stora mängder information. På Xerox PARC arbetade han med Scatter/Gather-systemet, som hierarkiskt klustrade en dokumentsamling och låter användaren samla kluster på olika nivåer och sprida dem igen. Mer nyligen [ när? ] han har forskat på hämtningssystem som anpassar sig själva för att bäst passa deras individuella användares behov och beteenden, och har lett Haystack -projektet. David Karger är också en del av Confer: ett verktyg för konferensdeltagare som används av många forskningskonferenser.

Utmärkelser

Kargers avhandling fick 1994 ACM:s doktorsavhandlingspris och Mathematical Programming Societys Tucker-pris 1997. Han fick också National Academy of Sciences 2004 pris för initiativ inom forskning.

Personlig

Karger är gift med Allegra Goodman , en amerikansk författare. Paret bor i Cambridge, Massachusetts och har fyra barn, tre pojkar och en flicka.