David Karger
{{short description|American computer scientist}}
{{Infobox scientist
| name = David Karger
| birth_date = {{birth date and age|1967|05|01}}
| birth_name = David Ron Karger
| native_name =
| native_name_lang =
| image =
| image_size =
| alt =
| caption =
| other_names =
| residence =
| citizenship =
| nationality =
| fields = Information Management
Human-Computer Interaction
Semantic Web
PIM{{GoogleScholar|2vQRGrYAAAAJ}}
| workplaces = Harvard University
Stanford University
MIT
Xerox PARC
| alma_mater = Harvard University
Stanford University
| thesis_title = Random Sampling in Graph Optimization Problems
| thesis_url = http://people.csail.mit.edu/karger/Papers/thesis.pdf
| thesis_year = 1995
| doctoral_advisor = Rajeev Motwani{{MathGenealogy|id=39231}}
| academic_advisors =
| doctoral_students = {{plainlist|1=
}}
| notable_students =
| known_for = Karger's algorithm
Chord (peer-to-peer)
Consistent hashing
| author_abbrev_bot =
| author_abbrev_zoo =
| influences =
| influenced =
| awards = ACM Fellow
| signature =
| signature_alt =
| website = {{URL|http://people.csail.mit.edu/karger}}
| footnotes =
| spouse = Allegra Goodman
| children =
}}
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.
Education
Karger received a Bachelor of Arts degree from Harvard University and a PhD in computer science from Stanford University.{{cite web|title=David Karger CSAIL|url=http://www.csail.mit.edu/user/1542|access-date=13 March 2011}}
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.{{cite web|last=Karger|first=David|title=Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm|url=http://people.csail.mit.edu/karger/Papers/mincut.ps|publisher=Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1993}} 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.{{Cite journal | last1 = Karger | first1 = D. R. | last2 = Klein | first2 = P. N. | last3 = Tarjan | first3 = R. E. | doi = 10.1145/201019.201022 | title = A randomized linear-time algorithm to find minimum spanning trees | journal = Journal of the ACM | volume = 42 | issue = 2 | pages = 321 | year = 1995 | citeseerx = 10.1.1.39.9012 | s2cid = 832583 }} With Ion Stoica, Robert Morris, Frans Kaashoek, and Hari Balakrishnan, he also developed Chord, one of the four original distributed hash table protocols.{{Cite journal | last1 = Stoica | first1 = I. | author-link1 = Ion Stoica| last2 = Morris | first2 = R. | last3 = Karger | first3 = D. | author-link3 = David Karger| last4 = Kaashoek | first4 = M. F. | last5 = Balakrishnan | first5 = H. | author-link5 = Hari Balakrishnan| title = Chord: A scalable peer-to-peer lookup service for internet applications| doi = 10.1145/964723.383071 | journal = ACM SIGCOMM Computer Communication Review | volume = 31 | issue = 4 | pages = 149 | year = 2001 | url = http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf}}
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.{{Cite book | last1 = Cutting | first1 = D. R. | last2 = Karger | first2 = D. R. | last3 = Pedersen | first3 = J. O. | last4 = Tukey | first4 = J. W. | chapter = Scatter/Gather: a cluster-based approach to browsing large document collections | doi = 10.1145/133160.133214 | title = Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval - SIGIR '92 | pages = 318 | year = 1992 | isbn = 978-0897915236 | citeseerx = 10.1.1.34.6746 | s2cid = 373655 }} More recently{{When|date=September 2013}} 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{{cite web|title=David Karger|url=https://awards.acm.org/award_winners/karger_3831799|access-date=2021-01-23|website=Awards Home|publisher=Association for Computing Machinery|language=en}} and the Mathematical Programming Society's 1997 Tucker Prize.{{cite web|title=A.W. Tucker Prize - Past Winners|url=http://www.mathopt.org/?nav=tucker|website=Mathematical Optimization Society Prizes|publisher=Mathematical Optimization Society|language=en}} He also received the National Academy of Sciences' 2004 Award for Initiative in Research.{{cite web|title=William O. Baker Award for Initiatives in Research Recipients|url=http://www.nasonline.org/programs/awards/initiatives-in-research.html|website=About the William O. Baker Award for Initiatives in Research|publisher=National Academy of Sciences|language=en}}
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.{{cite web |title=About Allegra |url=http://www.allegragoodman.com/goodman-biography.htm |access-date=13 March 2011 |url-status=dead |archive-url=https://web.archive.org/web/20110624093715/http://www.allegragoodman.com/goodman-biography.htm |archive-date=24 June 2011 }}
References
{{reflist}}
{{Authority control}}
{{DEFAULTSORT:Karger, David}}
Category:People in information technology
Category:American computer scientists
Category:American Orthodox Jews
Category:Jewish American scientists
Category:Harvard University alumni
Category:Stanford University alumni