Difference between revisions of "Jon Kleinberg"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
(2 intermediate revisions by the same user not shown) | |||
Line 5: | Line 5: | ||
'''Jon Michael Kleinberg''',<br/> | '''Jon Michael Kleinberg''',<br/> | ||
an American mathematician, computer scientist and professor at [https://en.wikipedia.org/wiki/Cornell_University Cornell University]. His research focuses on the interaction of [[Algorithms|algorithms]] and [https://en.wikipedia.org/wiki/Complex_network networks], | an American mathematician, computer scientist and professor at [https://en.wikipedia.org/wiki/Cornell_University Cornell University]. His research focuses on the interaction of [[Algorithms|algorithms]] and [https://en.wikipedia.org/wiki/Complex_network 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 [[Mathematician#MXGoemans|Michel Goemans]] <ref>[[Jon Kleinberg]] ('''1996'''). ''[https://dl.acm.org/doi/book/10.5555/923845 Approximation Algorithms for Disjoint Paths Problems]''. Ph.D. thesis, [[Massachusetts Institute of Technology]], advisor [[Mathematician#MXGoemans|Michel Goemans]]</ref>, | + | 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 [[Mathematician#MXGoemans|Michel Goemans]] <ref>[[Jon Kleinberg]] ('''1996'''). ''[https://dl.acm.org/doi/book/10.5555/923845 Approximation Algorithms for Disjoint Paths Problems]''. Ph.D. thesis, [[Massachusetts Institute of Technology]], advisor [[Mathematician#MXGoemans|Michel Goemans]]</ref>, and is in particular known for the development of the [https://en.wikipedia.org/wiki/HITS_algorithm HITS algorithm] <ref>[[Jon Kleinberg]] ('''1999'''). ''[http://cs.brown.edu/memex/ACM_HypertextTestbed/papers/10.html Hubs, Authorities, and Communities]''. [[ACM#Surveys|ACM Computing Surveys]], Vol. 31, No. 4</ref>. 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 Networks|neural network]] chess engine <ref>[https://maiachess.com/ Maia Chess]</ref>. |
− | and is in particular known for the development of the [https://en.wikipedia.org/wiki/HITS_algorithm HITS algorithm]. 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 Networks|neural network]] chess engine <ref>[https://maiachess.com/ Maia Chess]</ref>. | ||
=Selected Publications= | =Selected Publications= | ||
Line 18: | Line 17: | ||
* [[Jon Kleinberg]], [[Mathematician#MXGoemans|Michel Goemans]] ('''1998'''). ''[https://epubs.siam.org/doi/abs/10.1137/S0895480195287541?mobileUi=0 The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover]''. [https://en.wikipedia.org/wiki/SIAM_Journal_on_Discrete_Mathematics SIAM Journal on Discrete Mathematics], Vol. 11, No. 2, [https://math.mit.edu/~goemans/PAPERS/KleinbergG-1998-TheLovaszThetaFunctionVertexCover.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Lov%C3%A1sz_number Lovász number from Wikipedia]</ref> | * [[Jon Kleinberg]], [[Mathematician#MXGoemans|Michel Goemans]] ('''1998'''). ''[https://epubs.siam.org/doi/abs/10.1137/S0895480195287541?mobileUi=0 The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover]''. [https://en.wikipedia.org/wiki/SIAM_Journal_on_Discrete_Mathematics SIAM Journal on Discrete Mathematics], Vol. 11, No. 2, [https://math.mit.edu/~goemans/PAPERS/KleinbergG-1998-TheLovaszThetaFunctionVertexCover.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Lov%C3%A1sz_number Lovász number from Wikipedia]</ref> | ||
* [[Mathematician#MXGoemans|Michel Goemans]], [[Jon Kleinberg]] ('''1998'''). ''[https://link.springer.com/article/10.1007/BF01585867 An improved approximation ratio for the minimum latency problem]''. [https://en.wikipedia.org/wiki/Mathematical_Programming Mathematical Programming], Vol. 82, [http://math.mit.edu/~goemans/PAPERS/latency.pdf pdf] | * [[Mathematician#MXGoemans|Michel Goemans]], [[Jon Kleinberg]] ('''1998'''). ''[https://link.springer.com/article/10.1007/BF01585867 An improved approximation ratio for the minimum latency problem]''. [https://en.wikipedia.org/wiki/Mathematical_Programming Mathematical Programming], Vol. 82, [http://math.mit.edu/~goemans/PAPERS/latency.pdf pdf] | ||
− | * [[Jon Kleinberg]] ('''1999'''). ''[http://cs.brown.edu/memex/ACM_HypertextTestbed/papers/10.html Hubs, Authorities, and Communities]''. [[ACM#Surveys|ACM Computing Surveys]], Vol. 31, No. 4 | + | * [[Jon Kleinberg]] ('''1999'''). ''[http://cs.brown.edu/memex/ACM_HypertextTestbed/papers/10.html Hubs, Authorities, and Communities]''. [[ACM#Surveys|ACM Computing Surveys]], Vol. 31, No. 4 <ref>[https://en.wikipedia.org/wiki/HITS_algorithm HITS algorithm from Wikipedia]</ref> |
* [[Jon Kleinberg]] ('''1999'''). ''[https://dl.acm.org/doi/10.1145/324133.324140 Authoritative sources in a hyperlinked environment]''. [[ACM#Journal|Journal of the ACM]], Vol. 46, No. 5 | * [[Jon Kleinberg]] ('''1999'''). ''[https://dl.acm.org/doi/10.1145/324133.324140 Authoritative sources in a hyperlinked environment]''. [[ACM#Journal|Journal of the ACM]], Vol. 46, No. 5 | ||
==2000 ...== | ==2000 ...== | ||
− | * [[Jon Kleinberg]] ('''2000'''). ''[https://dl.acm.org/doi/10.1145/335305.335325 The small-world phenomenon: an algorithmic perspective]''. [https://dblp.org/db/conf/stoc/stoc2000.html#Kleinberg00 STOC 2000], [https://www.cs.cornell.edu/home/kleinber/swn.pdf pdf] | + | * [[Jon Kleinberg]] ('''2000'''). ''[https://dl.acm.org/doi/10.1145/335305.335325 The small-world phenomenon: an algorithmic perspective]''. [https://dblp.org/db/conf/stoc/stoc2000.html#Kleinberg00 STOC 2000], [https://www.cs.cornell.edu/home/kleinber/swn.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Small-world_network Small-world network from Wikipedia]</ref> <ref>[https://en.wikipedia.org/wiki/Small-world_experiment Small-world experiment from Wikipedia]</ref> |
* [[Jon Kleinberg]] ('''2000'''). ''[https://projecteuclid.org/euclid.im/1057768559 Detecting a Network Failure]''. [https://dblp.org/db/conf/focs/focs2000.html#Kleinberg00 FOCS 2000] | * [[Jon Kleinberg]] ('''2000'''). ''[https://projecteuclid.org/euclid.im/1057768559 Detecting a Network Failure]''. [https://dblp.org/db/conf/focs/focs2000.html#Kleinberg00 FOCS 2000] | ||
− | * [[Jon Kleinberg]], [[Mathematician#YRabani|Yuval Rabani]], [[Mathematician#ETardos|Éva Tardos]] ('''2001'''). ''[https://dl.acm.org/doi/10.1006/jcss.2001.1752 Fairness in Routing and Load Balancing]''. [https://en.wikipedia.org/wiki/Journal_of_Computer_and_System_Sciences JCSS], Vol. 63, No. 1, [https://www.cs.huji.ac.il/~yrabani/Papers/KleinbergRT-JCSS-revised.pdf pdf] | + | * [[Jon Kleinberg]], [[Mathematician#YRabani|Yuval Rabani]], [[Mathematician#ETardos|Éva Tardos]] ('''2001'''). ''[https://dl.acm.org/doi/10.1006/jcss.2001.1752 Fairness in Routing and Load Balancing]''. [https://en.wikipedia.org/wiki/Journal_of_Computer_and_System_Sciences JCSS], Vol. 63, No. 1, [https://www.cs.huji.ac.il/~yrabani/Papers/KleinbergRT-JCSS-revised.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Routing Routing from Wikipedia]</ref> <ref>[https://en.wikipedia.org/wiki/Load_balancing_(computing) Load balancing (computing) from Wikipedia]</ref> |
* [http://david-kempe.com/ David Kempe], [[Jon Kleinberg]], [[Mathematician#ETardos|Éva Tardos]] ('''2001'''). ''[https://dl.acm.org/doi/10.1145/956750.956769 Maximizing the spread of influence through a social network]''. [https://dblp.org/db/conf/kdd/kdd2003.html#KempeKT03 KDD 2003], [https://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf pdf] | * [http://david-kempe.com/ David Kempe], [[Jon Kleinberg]], [[Mathematician#ETardos|Éva Tardos]] ('''2001'''). ''[https://dl.acm.org/doi/10.1145/956750.956769 Maximizing the spread of influence through a social network]''. [https://dblp.org/db/conf/kdd/kdd2003.html#KempeKT03 KDD 2003], [https://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf pdf] | ||
* [[Mathematician#DLibenNowell|David Liben-Nowell]], [[Jon Kleinberg]] ('''2003'''). ''The link prediction problem for social networks''. [https://dblp.org/db/conf/cikm/cikm2003.html#Liben-NowellK03 CIKM 2003], [https://www.cs.cornell.edu/home/kleinber/link-pred.pdf pdf] | * [[Mathematician#DLibenNowell|David Liben-Nowell]], [[Jon Kleinberg]] ('''2003'''). ''The link prediction problem for social networks''. [https://dblp.org/db/conf/cikm/cikm2003.html#Liben-NowellK03 CIKM 2003], [https://www.cs.cornell.edu/home/kleinber/link-pred.pdf pdf] | ||
* [[Mathematician#JLeskovec|Jure Leskovec]], [[Mathematician#DChakrabarti|Deepayan Chakrabarti]], [[Jon Kleinberg]], [[Mathematician#CNFaloutsos|Christos Faloutsos]] ('''2005'''). ''[https://link.springer.com/chapter/10.1007/11564126_17 Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication]''. [https://dblp.org/db/conf/pkdd/pkdd2005.html#LeskovecCKF05 PKDD 2005], [https://cs.stanford.edu/~jure/pubs/kronecker-pkdd05.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Kronecker_product Kronecker product from Wikipedia]</ref> | * [[Mathematician#JLeskovec|Jure Leskovec]], [[Mathematician#DChakrabarti|Deepayan Chakrabarti]], [[Jon Kleinberg]], [[Mathematician#CNFaloutsos|Christos Faloutsos]] ('''2005'''). ''[https://link.springer.com/chapter/10.1007/11564126_17 Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication]''. [https://dblp.org/db/conf/pkdd/pkdd2005.html#LeskovecCKF05 PKDD 2005], [https://cs.stanford.edu/~jure/pubs/kronecker-pkdd05.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Kronecker_product Kronecker product from Wikipedia]</ref> | ||
* [[Jon Kleinberg]], [[Mathematician#ETardos|Éva Tardos]] ('''2006'''). ''[https://www.pearson.com/us/higher-education/program/Kleinberg-Algorithm-Design/PGM319216.html Algorithm Design]''. [https://en.wikipedia.org/wiki/Pearson_plc Pearson], [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley] | * [[Jon Kleinberg]], [[Mathematician#ETardos|Éva Tardos]] ('''2006'''). ''[https://www.pearson.com/us/higher-education/program/Kleinberg-Algorithm-Design/PGM319216.html Algorithm Design]''. [https://en.wikipedia.org/wiki/Pearson_plc Pearson], [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley] | ||
+ | * [[Mathematician#JLeskovec|Jure Leskovec]], [[Mathematician#DChakrabarti|Deepayan Chakrabarti]], [[Jon Kleinberg]], [[Mathematician#CNFaloutsos|Christos Faloutsos]], [[Mathematician#ZGhahramani|Zoubin Ghahramani]] ('''2008'''). ''Kronecker Graphs: An Approach to Modeling Networks''. [https://arxiv.org/abs/0812.4905 arXiv:0812.4905] <ref>[https://en.wikipedia.org/wiki/Kronecker_graph Kronecker graph from Wikipedia]</ref> | ||
==2010 ...== | ==2010 ...== | ||
* [[Mathematician#DAEasley|David A. Easley]], [[Jon Kleinberg]] ('''2010'''). ''[https://www.cs.cornell.edu/home/kleinber/networks-book/ Networks, Crowds, and Markets - Reasoning About a Highly Connected World]''. [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press] | * [[Mathematician#DAEasley|David A. Easley]], [[Jon Kleinberg]] ('''2010'''). ''[https://www.cs.cornell.edu/home/kleinber/networks-book/ Networks, Crowds, and Markets - Reasoning About a Highly Connected World]''. [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press] | ||
Line 35: | Line 35: | ||
* [[Ashton Anderson]], [[Mathematician#DPHuttenlocher|Daniel Huttenlocher]], [[Jon Kleinberg]], [[Mathematician#JLeskovec|Jure Leskovec]] ('''2014'''). ''Engaging with Massive Online Courses''. [https://arxiv.org/abs/1403.3100 arXiv:1403.3100] | * [[Ashton Anderson]], [[Mathematician#DPHuttenlocher|Daniel Huttenlocher]], [[Jon Kleinberg]], [[Mathematician#JLeskovec|Jure Leskovec]] ('''2014'''). ''Engaging with Massive Online Courses''. [https://arxiv.org/abs/1403.3100 arXiv:1403.3100] | ||
* [[Ashton Anderson]], [[Jon Kleinberg]], [[Sendhil Mullainathan]] ('''2016'''). ''Assessing Human Error Against a Benchmark of Perfection''. [[ACM#SIGKDD|ACM SIGKDD 2016]], [https://arxiv.org/abs/1606.04956 arXiv:1606.04956] | * [[Ashton Anderson]], [[Jon Kleinberg]], [[Sendhil Mullainathan]] ('''2016'''). ''Assessing Human Error Against a Benchmark of Perfection''. [[ACM#SIGKDD|ACM SIGKDD 2016]], [https://arxiv.org/abs/1606.04956 arXiv:1606.04956] | ||
+ | * [https://scholar.google.com/citations?user=tiE4g64AAAAJ&hl=en Maithra Raghu], [https://scholar.google.com/citations?user=ZZNxNAYAAAAJ&hl=en Alex Irpan], [[Mathematician#JAndreas|Jacob Andreas]], [[Mathematician#RKleinberg|Robert Kleinberg]], [[Quoc V. Le]], [[Jon Kleinberg]] ('''2017'''). ''Can Deep Reinforcement Learning Solve Erdos-Selfridge-Spencer Games?'' [https://arxiv.org/abs/1711.02301 arXiv:1711.02301] | ||
==2020 ...== | ==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|ACM SIGKDD 2020]], [https://arxiv.org/abs/2006.01855 arXiv:2006.01855] | * [[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|ACM SIGKDD 2020]], [https://arxiv.org/abs/2006.01855 arXiv:2006.01855] |
Latest revision as of 00:07, 8 December 2020
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
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