His research interests include combinatorics, graph theory, genomics, and operations research. He is the "k" in G. West. Peck, a pseudonym for a group of six mathematicians that includes Kleitman. Formerly a physics professor at Brandeis University, Kleitman was encouraged by Paul Erdős to change his field of study to mathematics.
Perhaps humorously, Erdős once asked him, "Why are you only a physicist?" Kleitman joined the applied mathematics faculty at Massachusetts Institute of Technology in 1966, and was promoted to professor in 1969.
Kleitman coauthored at least six papers with Erdős, giving him an Erdős number of 1. He was a math advisor and extra for the film Good Will Hunting.
Since Minnie Driver, who appeared in Good Will Hunting, also appeared in Sleepers with Kevin Bacon, Kleitman has a Bacon number of 2. Adding the two numbers results in an Erdős–Bacon number of 3, tied for lowest currently.