- unknown (b.)
His work in algorithms has focused on applications of randomization to optimization problems and led to significant progress on several core problems. Responsible for Karger's algorithm, a Monte Carlo method to compute the minimum cut of a connected graph. He developed the fastest minimum spanning tree algorithm to date along with Philip Klein, and Robert Tarjan., in which they found a linear time randomized algorithm based on a combination of Borůvka's algorithm and the reverse-delete algorithm. He also helped to develop Chord, one of the four original distributed hash table protocols. He has also conducted research in the area of information retrieval and personal information management, focusing 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 allows the user to gather clusters at different levels and rescatter them. Is researching retrieval systems that personalize themselves to best fit their individual users' needs and behaviors, leading the Haystack project.
Noted For:Helped develop the fastest minimum spanning tree algorithm to date
Category of Achievement: