Daniel Sleator

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Daniel Sleator
Born 10 December 1953 (1953-12-10) (age 63)
Residence Pittsburgh
Fields Computer Science
Institutions Carnegie Mellon University
Alma mater University of Illinois at Urbana-Champaign, Stanford University
Doctoral advisor Robert Tarjan
Notable awards Paris Kanellakis Award (1999)

Daniel Dominic Kaplan Sleator (born 10 December 1953 in St. Louis)[1] is a Professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States. In 1999, he won the ACM Paris Kanellakis Award (jointly with Robert Tarjan) for the splay tree data structure.[2]

He was one of the pioneers in amortized analysis of algorithms, early examples of which were the analyses of the move-to-front heuristic,[3] and splay trees.[4] He invented many data structures with Robert Tarjan, such as splay trees, link/cut trees, and skew heaps.

The Sleator and Tarjan paper on the move-to-front heuristic[3] first suggested the idea of comparing an online algorithm to an optimal offline algorithm, for which the term competitive analysis was later coined in a paper of Karlin, Manasse, Rudolph, and Sleator.[5] Sleator also developed the theory of link grammars, and the Serioso music analyzer for analyzing meter and harmony in written music.

Personal life[edit]

Sleator commercialized the volunteer-based Internet Chess Server into the Internet Chess Club despite outcry from fellow volunteers. The ICS has since become one of the most successful internet-based commercial chess servers.

He is the brother of William Sleator, who wrote science fiction for young adults.

From 2003 to 2008, Sleator co-hosted the progressive talk show Left Out on WRCT-FM with Carnegie Mellon University School of Computer Science faculty member Bob Harper.


  1. ^ American Men and Women of Science, Thomson Gale, 2004
  2. ^ Citation for Sleator and Tarjan Kanellakis Award
  3. ^ a b Sleator, Daniel D.; Tarjan, Robert E. (1985), "Amortized efficiency of list update and paging rules" (PDF), Communications of the ACM (Association for Computing Machinery), 28 (2): 202–208, doi:10.1145/2786.2793 
  4. ^ Sleator, Daniel D.; Tarjan, Robert E. (1985), "Self-Adjusting Binary Search Trees" (PDF), Journal of the ACM (Association for Computing Machinery), 32 (3): 652–686, doi:10.1145/3828.3835 
  5. ^ Karlin, Anna R.; Manasse, Mark S.; Rudolph, Larry; Sleator, Daniel D. (1988), "Competitive snoopy caching", Algorithmica, 3 (1): 79–119, doi:10.1007/BF01762111, MR 925479 

External links[edit]