David Karger
Encyclopedia
David Karger is a Professor of Computer Science and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL) at the Massachusetts Institute of Technology (MIT). He received an AB from Harvard University
and a PhD in computer science
from Stanford University
. Dr. Karger's dissertation received the 1994 ACM
doctoral dissertation award and the Mathematical Programming Society
's 1997 Tucker Prize. He also received the National Academy of Science's 2004 Award for Initiative in Research.
David 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. Dr. 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.
Dr. Karger has also 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.
Dr. Karger is married to Allegra Goodman
, an American author. The couple lives in Cambridge, Massachusetts and has four children, three boys and a girl.
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
and a PhD in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
from Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
. Dr. Karger's dissertation received the 1994 ACM
ACM
ACM is a three-letter acronym that may refer to:* Alkyl acrylate copolymer, a type of rubber commonly found in automotive transmissions and hoses* Arnold-Chiari malformation* Asbestos Containing Material* Association for Computing Machinery...
doctoral dissertation award and the Mathematical Programming Society
Mathematical Programming Society
Known as the Mathematical Programming Society until 2010, the Mathematical Optimization Society is an international association of researchers active in optimization...
's 1997 Tucker Prize. He also received the National Academy of Science's 2004 Award for Initiative in Research.
David 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
Karger's algorithm
In computer science and graph theory, the Karger's algorithm is a Monte Carlo method to compute the minimum cut of a connected graph developed by David Karger.-Algorithm:The idea of the algorithm is based on the concept of contraction of an edge e in a graph...
, a Monte Carlo method
Monte Carlo method
Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...
to compute the minimum cut
Minimum cut
In graph theory, a minimum cut of a graph is a cut whose cutset has the smallest number of elements or smallest sum of weights possible...
of a connected graph. Dr. Karger developed the fastest minimum spanning tree
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
algorithm to date with Philip Klein, and Robert Tarjan
Robert Tarjan
Robert Endre Tarjan is a renowned American computer scientist. He is the discoverer of several important graph algorithms, including Tarjan's off-line least common ancestors algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S...
. They found a linear time randomized algorithm
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
based on a combination of Borůvka's algorithm and the reverse-delete algorithm. With Ion Stoica, Robert Morris
Robert Tappan Morris
Robert Tappan Morris, , is an American computer scientist, best known for creating the Morris Worm in 1988, considered the first computer worm on the Internet - and subsequently becoming the first person convicted under the Computer Fraud and Abuse Act.He went on to co-found the online store...
, Frans Kaashoek, and Hari Balakrishnan
Hari Balakrishnan
Hari Balakrishnan is a Professor in the Department of Electrical Engineering and Computer Science at MIT. He is well-known for his contributions to computer networks and networked computer systems, including overlay and peer-to-peer networks, Internet routing and congestion control, wireless and...
, he also developed Chord, one of the four original distributed hash table
Distributed hash table
A distributed hash table is a class of a decentralized distributed system that provides a lookup service similar to a hash table; pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key...
protocols.
Dr. Karger has also conducted research in the area of information retrieval
Information retrieval
Information retrieval is the area of study concerned with searching for documents, for information within documents, and for metadata about documents, as well as that of searching structured storage, relational databases, and the World Wide Web...
and personal information management
Personal information management
Personal information management refers to the practice and the study of the activities people perform in order to acquire, organize, maintain, retrieve and use information items such as documents , web pages and email messages for everyday use to complete tasks and fulfill a person’s various...
. This work has focused on new interfaces and algorithms for helping people sift effectively through large masses of information. While at Xerox PARC
PARC
PARC or Parc may refer to:* PARC , the Palo Alto Research Center * PARC Management, a theme park and entertainment venue operator...
, 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
Haystack (PIM)
Haystack is a project at the Massachusetts Institute of Technology to research and develop several applications around personal information management and the Semantic Web. The most notable of those applications is the Haystack client, a research personal information manager and one of the first...
project.
Dr. Karger is married to Allegra Goodman
Allegra Goodman
Allegra Goodman is an American author based in Cambridge, Massachusetts. Her most recent novel, The Cookbook Collector, was published in 2010. Goodman wrote and illustrated her first novel at the age of seven. -Early years and family:...
, an American author. The couple lives in Cambridge, Massachusetts and has four children, three boys and a girl.