David Karger

David Karger
  • Position: Professor
  • Office: 32-G592
  • Phone: +1 (617) 258-6167
  • Email: karger@csail.mit.edu
  • Areas of Study: Theory, Algorithms, Personal Information Management
  • Personal Website
  • Last Update: October 2, 2013
  • Download vCard

Biography

David Karger (A.B. Summa cum laude in Computer Science, 1989, Harvard University, Ph.D., 1994, in Computer Science, Stanford University) is a Professor of Computer Science and a member of the Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology. Karger splits his research between algorithms and information retrieval. His work in algorithms has focused on applications of randomization to optimization problems and led to significant progress on several core problems. He has also researched applications of theoretical ideas to applied areas such as compilers and networks. His dissertation received the 1994 ACM doctoral dissertation award and the Mathematical Programming Society's 1997 Tucker Prize. His research in information retrieval has focused on new interfaces and algorithms for helping people sift effectively through large masses of information. His work on the Scatter/Gether browsing system at Xerox PARC led to two patents. More recently he has been researching retrieval systems that personalize themselves to best fit their individual users' needs and behaviors. He recently received the National Academy of Science's 2004 Award for Initiative in research.

David leads the Haystack group at CSAIL, which researches many facets of information management including capture, organization, retrieval, sharing, and visualization.

Projects

Publications

  • Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan, Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, ACM SIGCOMM 2001, San Deigo, CA, August 2001, pp. 149-160.
  • D.R. Karger, "Minimum Cuts in Near-Linear Time." Journal of the ACM 47(1):46--76, January 2000.
  • D.R. Karger, "A Randomized Fully Polynomial Approximation Scheme for the All Terminal Network Reliability Problem." SIAM Journal on Computing 29(2):492--514, 1999.
  • D.R. Karger, R. Motwani, and M. Sudan, "Approximate Graph Coloring by Semidefinite Programming." Journal of the ACM, 45(2):246--265,March 1998.
  • D. Cutting, D.R. Karger, J. Pederson, and J.W. Tukey, "Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections." In Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 318-329, Copenhagen, Denmark, 1992.

Awards

  • ACM Special Interest Group on Data Communications: Test of Time Award (2011)
  • Association for Computing Machinery: Fellow (2009)
  • Institute of Electrical and Electronics Engineers: William R. Bennett Prize Paper Award (2004)
  • National Academy of Sciences: Award for Initiatives in Research (2003)
  • USENIX Security: Best Student Paper Award (2002)
  • National Academy of Sciences: Award for Initiatives in Research (2002)
  • Packard Foundation: Packard Fellowship (1997)
  • National Science Foundation: Career Award (1995)
  • Association for Computing Machinery: Doctoral Dissertation Award (1994)