David Karger

David Karger
Born David Ron Karger
May 1, 1967
Fields Information Management
Human-Computer Interaction
Semantic Web
PIM[1]
Institutions Harvard University
Stanford University
MIT
Xerox PARC
Alma mater Harvard University
Stanford University
Thesis Random Sampling in Graph Optimization Problems (1995)
Doctoral advisor Rajeev Motwani[2]
Doctoral students Dennis Quan, Jr.
Harr Chen
Jonathan Feldman
Bernhard Haeupler
David Huynh
Nicole Immorlica
Matthew Levine
Maria Minkoff
Evdokia Nikolova
Matthias (Jan) Ruhl
Lawrence Shih
Vineet Sinha
Jaime Teevan
Max Van Kleek[2]
Known for Karger's algorithm
Website
people.csail.mit.edu/karger

David Ron Karger (born May 1, 1967) is a professor of computer science and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL) at the Massachusetts Institute of Technology.

Education

Karger received a Bachelor of Arts degree from Harvard University and a PhD in computer science from Stanford University.[3]

Research

Karger's work in algorithms has focused on applications of randomization to optimization problems and led to significant progress on several core problems. He is responsible for Karger's algorithm, a Monte Carlo method to compute the minimum cut of a connected graph.[4] Karger developed the fastest minimum spanning tree algorithm to date with Philip Klein, and Robert Tarjan. They found a linear time randomized algorithm based on a combination of Borůvka's algorithm and the reverse-delete algorithm.[5] With Ion Stoica, Robert Morris, Frans Kaashoek, and Hari Balakrishnan, he also developed Chord, one of the four original distributed hash table protocols.[6]

Karger has conducted research in the area of information retrieval and personal information management. This work has focused on new interfaces and algorithms for helping people sift effectively through large masses of information. While at Xerox PARC, he worked on the Scatter/Gather system, which hierarchically clustered a document collection and allow the user to gather clusters at different levels and rescatter them.[7] More recently he has been researching retrieval systems that personalize themselves to best fit their individual users' needs and behaviors, leading the Haystack project. David Karger is also part of Confer: a tool for conference attendees used by many research conferences.

Awards

Karger's dissertation received the 1994 ACM doctoral dissertation award and the Mathematical Programming Society's 1997 Tucker Prize. He also received the National Academy of Science's 2004 Award for Initiative in Research.

Personal

Karger is married to Allegra Goodman, an American author. The couple live in Cambridge, Massachusetts and have four children, three boys and a girl.[8]

References

  1. ↑ David Karger's publications indexed by Google Scholar, a free service provided by Google
  2. ↑ 2.0 2.1 David Karger at the Mathematics Genealogy Project
  3. ↑ "David Karger CSAIL". Retrieved 13 March 2011.
  4. ↑ Karger, David. "Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm". Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1993.
  5. ↑ Karger, D. R.; Klein, P. N.; Tarjan, R. E. (1995). "A randomized linear-time algorithm to find minimum spanning trees". Journal of the ACM 42 (2): 321. doi:10.1145/201019.201022.
  6. ↑ Stoica, I.; Morris, R.; Karger, D.; Kaashoek, M. F.; Balakrishnan, H. (2001). "Chord: A scalable peer-to-peer lookup service for internet applications" (PDF). ACM SIGCOMM Computer Communication Review 31 (4): 149. doi:10.1145/964723.383071.
  7. ↑ Cutting, D. R.; Karger, D. R.; Pedersen, J. O.; Tukey, J. W. (1992). "Scatter/Gather: a cluster-based approach to browsing large document collections". Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval - SIGIR '92. p. 318. doi:10.1145/133160.133214. ISBN 0897915232.
  8. ↑ "About Allegra". Retrieved 13 March 2011.