David Karger

From Wikipedia, the free encyclopedia

Template:Short description Script error: No such module "Template wrapper".Script error: No such module "Check for conflicting parameters".

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

Early life and education

Karger was born and raised in Brookline, Massachusetts.[1] His father served in the Israel Defense Forces before immigrating to the United States, and worked at MIT Lincoln Laboratories.[2][3] He received a Bachelor of Arts degree from Harvard University in 1989, completed Part III at Cambridge in 1990, and received a PhD in computer science from Stanford University in 1994 advised by Rajeev Motwani.[4][5]

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.[6] 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.[7] With Ion Stoica, Robert Morris, Frans Kaashoek, and Hari Balakrishnan, he also developed Chord, one of the four original distributed hash table protocols.[8]

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.[9] More recently[when?] 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[10] and the Mathematical Programming Society's 1997 Tucker Prize.[11] He also received the National Academy of Sciences' 2004 Award for Initiative in Research.[12]

Personal

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

References

Page Template:Reflist/styles.css has no content.

  1. ^ Page Module:Citation/CS1/styles.css has no content.Heinemann, Lynn (2006-03-01). "Karger moves in the best circles". MIT News.
  2. ^ Page Module:Citation/CS1/styles.css has no content.Bartle, Jay (2012-08-28). "ARIEH KARGER Obituary (2012)". Legacy.com.
  3. ^ Page Module:Citation/CS1/styles.css has no content."Arieh Karger Obituary". Dignity Memorial. 1937-10-29.
  4. ^ Page Module:Citation/CS1/styles.css has no content."David Karger CSAIL". Retrieved 13 March 2011.
  5. ^ Page Module:Citation/CS1/styles.css has no content."David R. Karger" (PDF).
  6. ^ Page Module:Citation/CS1/styles.css has no content.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.
  7. ^ Page Module:Citation/CS1/styles.css has no content.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. CiteSeerX 10.1.1.39.9012. doi:10.1145/201019.201022. S2CID 832583.
  8. ^ Page Module:Citation/CS1/styles.css has no content.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.
  9. ^ Page Module:Citation/CS1/styles.css has no content.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. CiteSeerX 10.1.1.34.6746. doi:10.1145/133160.133214. ISBN 978-0897915236. S2CID 373655.
  10. ^ Page Module:Citation/CS1/styles.css has no content."David Karger". Awards Home. Association for Computing Machinery. Retrieved 2021-01-23.
  11. ^ Page Module:Citation/CS1/styles.css has no content."A.W. Tucker Prize - Past Winners". Mathematical Optimization Society Prizes. Mathematical Optimization Society.
  12. ^ Page Module:Citation/CS1/styles.css has no content."William O. Baker Award for Initiatives in Research Recipients". About the William O. Baker Award for Initiatives in Research. National Academy of Sciences.
  13. ^ Page Module:Citation/CS1/styles.css has no content."About Allegra". Archived from the original on 24 June 2011. Retrieved 13 March 2011.

Lua error in package.lua at line 80: module 'Module:Authority control/config' not found.

Retrieved from "https://cosmopedia.co/index.php?title=David_Karger&oldid=9749334"