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