David Ron Karger (born May 1, 1967) is a professor of computer science and a member of the Computer Science and Artificial Intelligence Laboratory (
CSAIL
Computer Science and Artificial Intelligence Laboratory (CSAIL) is a research institute at the Massachusetts Institute of Technology (MIT) formed by the 2003 merger of the Laboratory for Computer Science (LCS) and the Artificial Intelligence Lab ...
) at the
Massachusetts Institute of Technology
The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the ...
.
Education
Karger received a
Bachelor of Arts
Bachelor of arts (BA or AB; from the Latin ', ', or ') is a bachelor's degree awarded for an undergraduate program in the arts, or, in some cases, other disciplines. A Bachelor of Arts degree course is generally completed in three or four year ...
degree from
Harvard University
Harvard University is a private Ivy League research university in Cambridge, Massachusetts. Founded in 1636 as Harvard College and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of high ...
and a PhD in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
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
In computer science and graph theory, Karger's algorithm is a randomized algorithm to compute a minimum cut of a connected graph. It was invented by David Karger and first published in 1993.
The idea of the algorithm is based on the concept of ...
, a
Monte Carlo method
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be determi ...
to compute the
minimum cut
In graph theory, a minimum cut or min-cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets) that is minimal in some metric.
Variations of the minimum cut problem consider weighted graphs, directed graphs, ter ...
of a connected graph. Karger developed the fastest
minimum spanning tree
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...
algorithm to date, with Philip Klein and
Robert Tarjan
Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician. He is the discoverer of several graph algorithms, including Tarjan's off-line lowest common ancestors algorithm, and co-inventor of both splay trees ...
Borůvka's algorithm
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph,
or a minimum spanning forest in the case of a graph that is not connected.
It was first published in 1926 by Otakar Borůvka as a method of constructing ...
and the reverse-delete algorithm. With
Ion Stoica
Ion Stoica is a Romanian-American computer scientist specializing in distributed systems, cloud computing and computer networking. He is a professor of computer science at the University of California, Berkeley and co-director of AMPLab. He co-fo ...
distributed hash table
A distributed hash table (DHT) is a distributed system that provides a lookup service similar to a hash table: key–value pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key. The ...
personal information management
Personal information management (PIM) is the study of the activities people perform in order to acquire or create, store, organize, maintain, retrieve, and use information items such as documents (paper-based and digital), web pages, and email mes ...
. This work has focused on new interfaces and algorithms for helping people sift effectively through large masses of information. While at
Xerox PARC
PARC (Palo Alto Research Center; formerly Xerox PARC) is a research and development company in Palo Alto, California. Founded in 1969 by Jacob E. "Jack" Goldman, chief scientist of Xerox Corporation, the company was originally a division of Xero ...
, 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
Hay is grass, legumes, or other herbaceous plants that have been cut and dried to be stored for use as animal fodder, either for large grazing animals raised as livestock, such as cattle, horses, goats, and sheep, or for smaller domesticated ...
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 and the
Allegra Goodman
Allegra Goodman (born 1967) is an American author based in Cambridge, Massachusetts. Goodman wrote and illustrated her first novel at the age of seven.
Biography
Allegra Goodman was born in Brooklyn, New York, and raised in Hawaii. The daughter ...
, an American author. The couple live in
Cambridge, Massachusetts
Cambridge ( ) is a city in Middlesex County, Massachusetts, United States. As part of the Boston metropolitan area, the cities population of the 2020 U.S. census was 118,403, making it the fourth most populous city in the state, behind Boston ...