# Jon Kleinberg

Revision as of 23:07, 7 December 2020 by GerdIsenberg (talk | contribs)

**Jon Michael Kleinberg**,

an American mathematician, computer scientist and professor at Cornell University. His research focuses on the interaction of algorithms and networks,
and the roles they play in large-scale social and information systems. He defended his Ph.D. thesis on *Approximation Algorithms for Disjoint Paths Problems* in 1996 at Massachusetts Institute of Technology under Michel Goemans ^{[2]}, and is in particular known for the development of the HITS algorithm ^{[3]}. Along with Reid McIlroy-Young, Russell Wang, Siddhartha Sen and Ashton Anderson, Jon Kleinberg is involved in the Maia Chess project of a human-like neural network chess engine ^{[4]}.

## Contents

# Selected Publications

^{[5]} ^{[6]}

## 1992 ...

- Daniel Huttenlocher, Klara Kedem, Jon Kleinberg (
**1992**).*On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane*. SCG 92^{[7]}^{[8]}^{[9]}^{[10]} - Jon Kleinberg, Éva Tardos (
**1995**).*Disjoint Paths in Densely Embedded Graphs*. FOCS 1995, pdf - Jon Kleinberg, Éva Tardos (
**1995**).*Approximations for the disjoint paths problem in high-diameter planar networks*. STOC 1995 - Jon Kleinberg (
**1996**).*Approximation Algorithms for Disjoint Paths Problems*. Ph.D. thesis, Massachusetts Institute of Technology, advisor Michel Goemans - Jon Kleinberg (
**1997**).*Two algorithms for nearest-neighbor search in high dimensions*. STOC 97, pdf^{[11]} - Jon Kleinberg, Michel Goemans (
**1998**).*The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover*. SIAM Journal on Discrete Mathematics, Vol. 11, No. 2, pdf^{[12]} - Michel Goemans, Jon Kleinberg (
**1998**).*An improved approximation ratio for the minimum latency problem*. Mathematical Programming, Vol. 82, pdf - Jon Kleinberg (
**1999**).*Hubs, Authorities, and Communities*. ACM Computing Surveys, Vol. 31, No. 4^{[13]} - Jon Kleinberg (
**1999**).*Authoritative sources in a hyperlinked environment*. Journal of the ACM, Vol. 46, No. 5

## 2000 ...

- Jon Kleinberg (
**2000**).*The small-world phenomenon: an algorithmic perspective*. STOC 2000, pdf^{[14]}^{[15]} - Jon Kleinberg (
**2000**).*Detecting a Network Failure*. FOCS 2000 - Jon Kleinberg, Yuval Rabani, Éva Tardos (
**2001**).*Fairness in Routing and Load Balancing*. JCSS, Vol. 63, No. 1, pdf^{[16]}^{[17]} - David Kempe, Jon Kleinberg, Éva Tardos (
**2001**).*Maximizing the spread of influence through a social network*. KDD 2003, pdf - David Liben-Nowell, Jon Kleinberg (
**2003**).*The link prediction problem for social networks*. CIKM 2003, pdf - Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos (
**2005**).*Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication*. PKDD 2005, pdf^{[18]} - Jon Kleinberg, Éva Tardos (
**2006**).*Algorithm Design*. Pearson, Addison-Wesley - Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, Zoubin Ghahramani (
**2008**).*Kronecker Graphs: An Approach to Modeling Networks*. arXiv:0812.4905^{[19]}

## 2010 ...

- David A. Easley, Jon Kleinberg (
**2010**).*Networks, Crowds, and Markets - Reasoning About a Highly Connected World*. Cambridge University Press - Ashton Anderson, Daniel Huttenlocher, Jon Kleinberg, Jure Leskovec (
**2012**).*Effects of user similarity in social media*. WSDM '12, pdf - Ashton Anderson, Daniel Huttenlocher, Jon Kleinberg, Jure Leskovec (
**2012**).*Discovering value from community activity on focused question answering sites: a case study of stack overflow*. ACM SIGKDD 2012, pdf^{[20]} - Ashton Anderson, Daniel Huttenlocher, Jon Kleinberg, Jure Leskovec (
**2013**).*Steering user behavior with badges*. IW3C2, pdf - Ashton Anderson, Daniel Huttenlocher, Jon Kleinberg, Jure Leskovec (
**2014**).*Engaging with Massive Online Courses*. arXiv:1403.3100 - Ashton Anderson, Jon Kleinberg, Sendhil Mullainathan (
**2016**).*Assessing Human Error Against a Benchmark of Perfection*. ACM SIGKDD 2016, arXiv:1606.04956 - Maithra Raghu, Alex Irpan, Jacob Andreas, Robert Kleinberg, Quoc V. Le, Jon Kleinberg (
**2017**).*Can Deep Reinforcement Learning Solve Erdos-Selfridge-Spencer Games?*arXiv:1711.02301

## 2020 ...

- Reid McIlroy-Young, Siddhartha Sen, Jon Kleinberg, Ashton Anderson (
**2020**).*Aligning Superhuman AI with Human Behavior: Chess as a Model System*. In Proceedings of the 26th ACM SIGKDD 2020, arXiv:2006.01855 - Reid McIlroy-Young, Russell Wang, Siddhartha Sen, Jon Kleinberg, Ashton Anderson (
**2020**).*Learning Personalized Models of Human Behavior in Chess*. arXiv:2008.10086

# External Links

- Jon Kleinberg's Homepage
- Jon Kleinberg from Wikipedia
- Jon Kleinberg - Google Scholar
- Jon Kleinberg - The Mathematics Genealogy Project

# References

- ↑ Jon Kleinberg, ICM, Madrid 2006, Mathematical Research Institute of Oberwolfach, Photo by Gert-Martin Greuel, Wikimedia Commons
- ↑ Jon Kleinberg (
**1996**).*Approximation Algorithms for Disjoint Paths Problems*. Ph.D. thesis, Massachusetts Institute of Technology, advisor Michel Goemans - ↑ Jon Kleinberg (
**1999**).*Hubs, Authorities, and Communities*. ACM Computing Surveys, Vol. 31, No. 4 - ↑ Maia Chess
- ↑ Jon Kleinberg - Google Scholar
- ↑ dblp: Jon M. Kleinberg
- ↑ Voronoi diagram from Wikipedia
- ↑ Hausdorff distance from Wikipedia
- ↑ Rigid transformation from Wikipedia
- ↑ Davenport–Schinzel sequence from Wikipedia
- ↑ Nearest neighbor search from Wikipedia
- ↑ Lovász number from Wikipedia
- ↑ HITS algorithm from Wikipedia
- ↑ Small-world network from Wikipedia
- ↑ Small-world experiment from Wikipedia
- ↑ Routing from Wikipedia
- ↑ Load balancing (computing) from Wikipedia
- ↑ Kronecker product from Wikipedia
- ↑ Kronecker graph from Wikipedia
- ↑ Stack Overflow from Wikipedia