Jon Kleinberg

Last updated
Jon Kleinberg
Jon Kleinberg at Cornell.jpg
Kleinberg speaking at the Cornell/Microsoft Research International Symposium on Self-Organizing Online Communities
Born
Jon Michael Kleinberg

1971 (age 52–53)
Boston, Massachusetts
NationalityAmerican
Education Cornell University
Massachusetts Institute of Technology
Known for HITS algorithm
Awards
Scientific career
Fields Computer Science
Institutions
Thesis Approximation algorithms for disjoint paths problems  (1996)
Doctoral advisor Michel Goemans [2]
Website videolectures.net/jon_kleinberg
www.cs.cornell.edu/home/kleinber

Jon Michael Kleinberg (born 1971) is an American computer scientist and the Tisch University Professor of Computer Science and Information Science at Cornell University known for his work in algorithms and networks. [3] [4] [5] [6] [7] [8] [9] He is a recipient of the Nevanlinna Prize by the International Mathematical Union.

Contents

Early life and education

Jon Kleinberg was born in 1971 in Boston, Massachusetts to a mathematics professor father and a computer consultant mother. [10] He received a Bachelor of Science degree in computer science from Cornell University in 1993 and a PhD from Massachusetts Institute of Technology in 1996. He is the older brother of fellow Cornell computer scientist Robert Kleinberg.

Career

Since 1996 Kleinberg has been a professor in the Department of Computer Science at Cornell, as well as a visiting scientist at IBM's Almaden Research Center. His work has been supported by an NSF Career Award, an ONR Young Investigator Award, a MacArthur Foundation Fellowship, a Packard Foundation Fellowship, a Sloan Foundation Fellowship, and grants from Google, Yahoo!, and the NSF. He is a member of the National Academy of Engineering and the American Academy of Arts and Sciences. In 2011, he was elected to the United States National Academy of Sciences. [11] [12] In 2013 he became a fellow of the Association for Computing Machinery. [13]

Research

Kleinberg is best known for his work on networks. One of his best-known contributions is the HITS algorithm, developed while he was at IBM. HITS is an algorithm for web search that builds on the eigenvector-based methods used in algorithms and served as the full-scale model for PageRank by recognizing that web pages or sites should be considered important not only if they are linked to by many others (as in PageRank), but also if they link to many others. Search engines themselves are examples of sites that are important because they link to many others. Kleinberg realized that this generalization implies two different classes of important web pages, which he called "hubs" and "authorities". The HITS algorithm is an algorithm for automatically identifying the leading hubs and authorities in a network of hyperlinked pages.

Kleinberg is also known for his work on algorithmic aspects of the small world experiment. [14] He was one of the first to realize that Stanley Milgram's famous "six degrees" letter-passing experiment implied not only that there are short paths between individuals in social networks but also that people seem to be good at finding those paths, an apparently simple observation that turns out to have profound implications for the structure of the networks in question. The formal model in which Kleinberg studied this question is a two dimensional grid, where each node has both short-range connections (edges) to neighbours in the grid and long-range connections to nodes further apart. For each node v, a long-range edge between v and another node w is added with a probability that decays as the second power of the distance between v and w. This is generalized to a d-dimensional grid, where the probability decays as the d-th power of the distance.

Kleinberg has written numerous papers and articles as well as a textbook on computer algorithms, Algorithm Design, co-authored the first edition with Éva Tardos and sole authored the second edition. [5] [15] Among other honors, he received a MacArthur Foundation Fellowship also known as the "genius grant" in 2005 and the Nevanlinna Prize in 2006, an award that is given out once every four years along with the Fields Medal as the premier distinction in Computational Mathematics. [16] His new book is entitled "Networks, Crowds, and Markets: Reasoning About a Highly Connected World", published by Cambridge University Press in 2010. [17]

Cornell's Association of Computer Science Undergraduates awarded him the "Faculty of the Year" award in 2002. [18]

Related Research Articles

<span class="mw-page-title-main">Robert Tarjan</span> American computer scientist and mathematician

Robert Endre Tarjan is an American computer scientist and mathematician. He is the discoverer of several graph theory algorithms, including his strongly connected components algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University.

<span class="mw-page-title-main">Peter Shor</span> American mathematician

Peter Williston Shor is an American professor of applied mathematics at MIT. He is known for his work on quantum computation, in particular for devising Shor's algorithm, a quantum algorithm for factoring exponentially faster than the best currently-known algorithm running on a classical computer.

<span class="mw-page-title-main">Juris Hartmanis</span> American computer scientist (1928–2022)

Juris Hartmanis was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory".

<span class="mw-page-title-main">Sartaj Sahni</span> American computer scientist

Professor Sartaj Kumar Sahni is a computer scientist based in the United States, and is one of the pioneers in the field of data structures. He is a distinguished professor in the Department of Computer and Information Science and Engineering at the University of Florida.

<span class="mw-page-title-main">Peter J. Denning</span> American computer scientist and writer

Peter James Denning is an American computer scientist and writer. He is best known for pioneering work in virtual memory, especially for inventing the working-set model for program behavior, which addressed thrashing in operating systems and became the reference standard for all memory management policies. He is also known for his works on principles of operating systems, operational analysis of queueing network systems, design and implementation of CSNET, the ACM digital library, and codifying the great principles of computing. He has written numerous influential articles and books, including an overview of fundamental computer science principles, computational thinking, and his thoughts on innovation as a set of learnable practices.

Allan Bertram Borodin is a Canadian-American computer scientist who is a professor at the University of Toronto.

<span class="mw-page-title-main">Éva Tardos</span> Hungarian mathematician

Éva Tardos is a Hungarian mathematician and the Jacob Gould Schurman Professor of Computer Science at Cornell University.

<span class="mw-page-title-main">Leslie Valiant</span> British American computer scientist

Leslie Gabriel Valiant is a British American computer scientist and computational theorist. He was born to a chemical engineer father and a translator mother. He is currently the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University. Valiant was awarded the Turing Award in 2010, having been described by the A.C.M. as a heroic figure in theoretical computer science and a role model for his courage and creativity in addressing some of the deepest unsolved problems in science; in particular for his "striking combination of depth and breadth".

Aleksandr Aleksandrovich Razborov, sometimes known as Sasha Razborov, is a Soviet and Russian mathematician and computational theorist. He is Andrew McLeish Distinguished Service Professor at the University of Chicago.

<span class="mw-page-title-main">David Gries</span> American computer scientist

David Gries is an American computer scientist at Cornell University, United States mainly known for his books The Science of Programming (1981) and A Logical Approach to Discrete Math.

Daniel Alan Spielman has been a professor of applied mathematics and computer science at Yale University since 2006. As of 2018, he is the Sterling Professor of Computer Science at Yale. He is also the Co-Director of the Yale Institute for Network Science, since its founding, and chair of the newly established Department of Statistics and Data Science.

<span class="mw-page-title-main">Gábor Tardos</span> Hungarian mathematician

Gábor Tardos is a Hungarian mathematician, currently a professor at Central European University and previously a Canada Research Chair at Simon Fraser University. He works mainly in combinatorics and computer science. He is the younger brother of Éva Tardos.

<span class="mw-page-title-main">Jennifer Tour Chayes</span> American computer scientist and mathematician

Jennifer Tour Chayes is dean of the college of computing, data science, and society at the University of California, Berkeley. Before joining Berkeley, she was a technical fellow and managing director of Microsoft Research New England in Cambridge, Massachusetts, which she founded in 2008, and Microsoft Research New York City, which she founded in 2012.

<span class="mw-page-title-main">Cynthia Dwork</span> American computer scientist

Cynthia Dwork is an American computer scientist best known for her contributions to cryptography, distributed computing, and algorithmic fairness. She is one of the inventors of differential privacy and proof-of-work.

Robert David Kleinberg is an American theoretical computer scientist and professor of Computer Science at Cornell University.

<span class="mw-page-title-main">Tim Roughgarden</span> American computer scientist

Timothy Avelin Roughgarden is an American computer scientist and a professor of Computer Science at Columbia University. Roughgarden's work deals primarily with game theoretic questions in computer science.

Kenneth P. Birman is a professor in the Department of Computer Science at Cornell University. He currently holds the N. Rama Rao Chair in Computer Science.

<span class="mw-page-title-main">Monika Henzinger</span> German computer scientist

Monika Henzinger is a German computer scientist, and is a former director of research at Google. She is currently a professor at the University of Vienna. Her expertise is mainly on algorithms with a focus on data structures, algorithmic game theory, information retrieval, search algorithms and Web data mining. She is married to Thomas Henzinger and has three children.

Katrina Ligett is an American computer scientist. She is a Professor of computer science at the Hebrew University and Visiting Associate at California Institute of Technology. She is known for work on algorithmic game theory and privacy.

<span class="mw-page-title-main">Jure Leskovec</span> Slovene computer scientist

Jure Leskovec is a Slovenian computer scientist, entrepreneur and associate professor of Computer Science at Stanford University focusing on networks. He was the chief scientist at Pinterest.

References

  1. ↑ "ACM Awards". Archived from the original on 2012-05-04. Retrieved 2013-05-08.
  2. ↑ Jon Kleinberg at the Mathematics Genealogy Project
  3. ↑ Kleinberg, J. M. (1999). "Authoritative sources in a hyperlinked environment". Journal of the ACM. 46 (5): 604. CiteSeerX   10.1.1.54.8485 . doi:10.1145/324133.324140. S2CID   221584113.
  4. ↑ Kleinberg, J. M. (2000). "Navigation in a small world". Nature. 406 (6798): 845. Bibcode:2000Natur.406..845K. doi: 10.1038/35022643 . PMID   10972276. S2CID   4425543.
  5. 1 2 Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design . Addison–Wesley, Boston. ISBN   978-0-321-29535-4.
  6. ↑ Jon M. Kleinberg at DBLP Bibliography Server OOjs UI icon edit-ltr-progressive.svg
  7. ↑ Jon Kleinberg's publications indexed by the Scopus bibliographic database. (subscription required)
  8. ↑ Jon Kleinberg author profile page at the ACM Digital Library
  9. ↑ Kempe, D.; Kleinberg, J.; Tardos, É. (2003). "Maximizing the spread of influence through a social network". Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '03. p. 137. CiteSeerX   10.1.1.14.6198 . doi:10.1145/956750.956769. ISBN   978-1581137378. S2CID   207732226.
  10. ↑ "ELMA BROTHERS MAKE A MARK IN CHEMISTRY AND MATH". 30 June 1989.
  11. ↑ Members and Foreign Associates Elected Archived 2011-05-07 at the Wayback Machine , National Academy of Sciences, May 3, 2011.
  12. ↑ Greuel, Gert-Martin; Hopcroft, John E.; Wright, Margaret H. (June–July 2007). "The Mathematical Work of Jon Kleinberg" (PDF). Notices of the American Mathematical Society . 54 (6): 740–743. Retrieved 2008-01-15.
  13. ↑ ACM Names Fellows for Computing Advances that Are Transforming Science and Society Archived 2014-07-22 at the Wayback Machine , Association for Computing Machinery, accessed 2013-12-10.
  14. ↑ Kleinberg, J. (2000). "The small-world phenomenon". Proceedings of the thirty-second annual ACM symposium on Theory of computing - STOC '00. p. 163. doi:10.1145/335305.335325. ISBN   978-1581131840. S2CID   221559836.
  15. ↑ Algorithm Design: 9780132131087: Computer Science Books @ Amazon.com
  16. ↑ "Jon Kleinberg receives international math prize".
  17. ↑ Kleinberg, Jon; Easley, David (2010). Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge, UK: Cambridge University Press. ISBN   978-0-521-19533-1.
  18. ↑ "Cornell CS Faculty Awards". Cornell University.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.