Jon Kleinberg

I am a professor at Cornell University. My research focuses on algorithms and networks, the roles they play in large-scale social and information systems, and their broader societal implications. My work has been supported by an NSF Career Award, an ONR Young Investigator Award, a MacArthur Foundation Fellowship, a Packard Foundation Fellowship, a Simons Investigator Award, a Sloan Foundation Fellowship, a Vannevar Bush Faculty Fellowship, and grants from Facebook, Google, Yahoo, the MacArthur and Simons Foundations, and the AFOSR, ARO, and NSF. I am a member of the National Academy of Sciences, the National Academy of Engineering, the American Academy of Arts and Sciences, and the American Philosophical Society.

Link to: Contact information.

Books and Teaching

• Since Spring 2021, Karen Levy and I have been teaching a course entitled Choices and Consequences in Computing (INFO 1260 / CS 1340). The course is designed at an introductory level with no formal prerequisites, and covers a range of ethical, societal, and policy implications of computing and information.
• D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.
  • This book is based on an inter-disciplinary course that we teach entitled Networks. The book, like the course, is designed at the introductory undergraduate level with no formal prerequisites. To support deeper explorations, most of the chapters are supplemented with optional advanced sections.
  • There is an on-line edX course based on the book: Networks, Crowds, and Markets, taught jointly with David Easley and Eva Tardos.
• J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.
  • This book is based on the undergraduate algorithms course that we both teach. We also use the more advanced parts for our graduate algorithms course.
• I teach a PhD-level course on network models, entitled The Structure of Information Networks (CS 6850).

Advising

• Current and former Ph.D. students: Anna Evtushenko, Katherine Van Koevering, Kate Donahue, Katy Blumer, Michela Meister, Kiran Tomlinson, Cazamere Comrie, Marios Papachristou, Yanbang Wang, Ben Laufer (co-adv. with Helen Nissenbaum), Emily Ryu (co-adv. with Eva Tardos), Kenny Peng (co-adv. with Nikhil Garg), Sophie Greenwood (co-adv. with Nikhil Garg), Manish Raghavan (2021 → MIT), Maithra Raghu (2020 → Google), Rediet Abebe (2019 → Berkeley; Harvard Society of Fellows), Rahmtin Rotabi (2017 → Google), Isabel Kloumann (2016 → Facebook), Johan Ugander (2014 → Stanford), Sigal Oren (2013 → Ben-Gurion Univ.), Daniel Romero (2012 → U. Michigan), Lars Backstrom (2009 → Facebook), Alex Slivkins (2006 → Microsoft Research), Mark Sandler (2006 → Google), Elliot Anshelevich (2005 → RPI), David Kempe (2003 → USC), Amit Kumar (2002 → IIT Delhi), Debra Goldberg (2001 → CU Boulder),

• Current and former postdocs: Harini Suresh, Lydia Liu (2024 → Princeton), Jonas Juul (2022 → Technical Univ. Denmark), Nate Veldt (2021 → TAMU), Hoda Heidari (2020 → CMU), Austin Benson (2018 → Cornell), Flavio Chierichetti (2012 → Sapienza University of Rome), Jure Leskovec (2009 → Stanford), Sid Suri (2008 → Microsoft Research), Gregory Kossinets. (2008 → Google), Mohammad Mahdian (2006 → Google), Frank McSherry (2003 → Microsoft Research), Anupam Gupta (2001 → CMU).

Research Papers

The papers below are also available in a chronological list. Additional bibliographic information can be found at DBLP and Google Scholar.

Recent Papers

• J. Kleinberg, S. Mullainathan. Language Generation in the Limit. Advances in Neural Information Processing Systems (NeurIPS) 38, 2024.
• Z. Tang, D. Jiao, R. McIlroy-Young, J. Kleinberg, S. Sen, A. Anderson. Maia-2: A Unified Model for Human-AI Alignment in Chess. Advances in Neural Information Processing Systems (NeurIPS) 38, 2024.
• K. Vafa, J.Y. Chen, J. Kleinberg, S. Mullainathan, A. Rambachan. Evaluating the World Model Implicit in a Generative Model. Advances in Neural Information Processing Systems (NeurIPS) 38, 2024.
• Y. Wang, H. Cui, J. Kleinberg. Microstructures and Accuracy of Graph Recall by Large Language Models. Advances in Neural Information Processing Systems (NeurIPS) 38, 2024.
• B. Laufer, J. Kleinberg, H. Heidari. Fine-Tuning Games: Bargaining and Adaptation for General-Purpose Models. Proc. 33rd International World Wide Web Conference, 2024.
• C. Dwork, C. Hays, J. Kleinberg, M. Raghavan. Content Moderation and the Formation of Online Communities: A Theoretical Framework. Proc. 33rd International World Wide Web Conference, 2024.
• K. Peng, M. Raghavan, E. Pierson, J. Kleinberg, N. Garg. Reconciling the accuracy-diversity trade-off in recommendations. Proc. 33rd International World Wide Web Conference, 2024.
• K. Hamade, R. McIlroy-Young, S. Sen, J. Kleinberg, A. Anderson. Designing Skill-Compatible AI: Methodologies and Frameworks in Chess. Proc 12th International Conference on Learning Representations (ICLR), 2024.
• Y. Wang, J. Kleinberg. From Graphs to Hypergraphs: Hypergraph Projection and its Remediation. Proc 12th International Conference on Learning Representations (ICLR), 2024.
• C. Dwork, C. Hays, J. Kleinberg, M. Raghavan. Equilibria, Efficiency, and Inequality in Network Formation for Hiring and Opportunity. Proc. 25th ACM Conference on Economics and Computation (EC), 2024.
• J. Kleinberg, S. Oren, E. Ryu, E. Tardos. Modeling reputation-based behavioral biases in school choice. Proc. 25th ACM Conference on Economics and Computation (EC), 2024.
• M. Meister, J. Kleinberg. Containing the spread of a contagion on a tree. Proc. 23rd Intl. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), 2024.
• K. Tomlinson, J. Ugander, J. Kleinberg. The Moderating Effect of Instant Runoff Voting. Proc. 38th AAAI Conference on Artificial Intelligence (AAAI-24), 2024.
• L.T. Liu, S. Barocas, J. Kleinberg, K. Levy. On the Actionability of Outcome Prediction. Proc. 38th AAAI Conference on Artificial Intelligence (AAAI-24), 2024.
• A. F. Cooper, K. Lee, M. Z. Choksi, S. Barocas, C. De Sa, J. Grimmelmann, J. Kleinberg, S. Sen, B. Zhang. Is My Prediction Arbitrary? The Confounding Effects of Variance in Fair Classification Benchmarks. Proc. 38th AAAI Conference on Artificial Intelligence (AAAI-24), 2024.
• J. Kleinberg, E. Ryu, E. Tardos. Calibrated Recommendations for Users with Decaying Attention. 17th International Symposium on Algorithmic Game Theory (SAGT), 2024.
• A. Hemida, A.B. Asghar, C. Kamhoua, J. Kleinberg. A Game-Theoretic Framework for Multi-Domain Cyber-Deception. Proc. IEEE European Symposium on Security and Privacy Workshops (EuroS&PW), 2024.
• J. Juul, A. Benson, J. Kleinberg. Hypergraph patterns and collaboration structure. Frontiers in Physics 11(2024).
• A. Evtushenko, J. Kleinberg. A comprehensive generalization of the Friendship Paradox to weights and attributes. Scientific Reports 14(13730), 2024.
• K. Tomlinson, T. Namjoshi, J. Ugander, J. Kleinberg. Replicating Electoral Success. arXiv/2402.17109, 2024.
• K. Van Koevering, J. Kleinberg. How Random is Random? Evaluating the Randomness and Humanness of LLMs' Coin Flips. arXiv/2406.00092, 2024.
• K. Van Koevering, M. Ye, J. Kleinberg. What's in a Niche? Migration Patterns in Online Communities. arXiv/2407.11794, 2024.
• K. Blumer, J. Kleinberg. Tracking Patterns in Toxicity and Antisocial Behavior Over User Lifetimes on Large Social Media Platforms. arXiv/2407.09365, 2024.

Web Analysis and Search: Hubs and Authorities

• J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). Also appears as IBM Research Report RJ 10076, May 1997.
• D. Gibson, J. Kleinberg, P. Raghavan. Inferring Web communities from link topology. Proc. 9th ACM Conference on Hypertext and Hypermedia, 1998.
• S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, P. Raghavan, S. Rajagopalan, Automatic resource list compilation by analyzing hyperlink structure and associated text. Proc. 7th International World Wide Web Conference, 1998.
• S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, Hypersearching the Web. Scientific American, June 1999.
• S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, Mining the link structure of the World Wide Web. IEEE Computer, August 1999.

Small-World Phenomena and Decentralized Search

• J. Kleinberg. Navigation in a Small World. Nature 406(2000), 845.
• J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000. Also appears as Cornell Computer Science Technical Report 99-1776 (October 1999). (Also in HTML.)
• J. Kleinberg. Small-World Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems 14, 2001.
• J. Kleinberg. The Small-World Phenomenon and Decentralized Search. A short essay as part of Math Awareness Month 2004, appearing in SIAM News 37(3), April 2004
• J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006.

Interactions of Algorithmic and Human Decision-Making

• C. Morewedge, S. Mullainathan, H.F. Naushan, C. Sunstein, J. Kleinberg, M. Raghavan, J. Ludwig. Human bias in algorithm design. Nature Human Behaviour, 7(2023).
• J. Kleinberg, J. Ludwig, S. Mullainathan, M. Raghavan. The Inversion Problem: Why Algorithms Should Infer Mental State and Not Just Predict Behavior. Perspectives on Psychological Science, 2023.
• J. Kleinberg, M. Raghavan, S. Mullainathan. The Challenge of Understanding What Users Want: Inconsistent Preferences and Engagement Optimization. Proc. 23rd ACM Conference on Economics and Computation (EC), 2022.
• D. Fudenberg, J. Kleinberg, A. Liang, S. Mullainathan. Measuring the Completeness of Economic Models. Journal of Political Economy, 2022.
• R. McIlroy-Young, R. Wang, S. Sen, J. Kleinberg, A. Anderson. Learning Models of Individual Behavior in Chess. Proc. 28th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2022.
• R. McIlroy-Young, J. Kleinberg, S. Sen, S. Barocas, A. Anderson. Mimetic Models: Ethical Implications of AI that Acts Like You. Proc. 5th AAAI/ACM Conference on Artificial Intelligence, Ethics, and Society (AIES), 2022.
• R. McIlroy-Young, R. Wang, S. Sen, J. Kleinberg, A. Anderson. Detecting Individual Decision-Making Style: Exploring Behavioral Stylometry in Chess. Advances in Neural Information Processing Systems (NeurIPS) 35, 2021.
• R. McIlroy-Young, S. Sen, J. Kleinberg, A. Anderson. Aligning Superhuman AI and Human Behavior: Chess as a Model System. Proc. 26th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2020.
  • See also the project page for the Maia Chess Engine, which is based on this work, and a Microsoft Research blog post about the project.

  M. Raghu, K. Blumer, R. Sayres, Z. Obermeyer, R. Kleinberg, S. Mullainathan, J. Kleinberg. Direct Uncertainty Prediction for Medical Second Opinions. Proc. 36th Intl. Conf. on Machine Learning (ICML), 2019. See also the accompanying blog post by Maithra Raghu.

  M. Yeomans, A. Shah., S. Mullainathan, J. Kleinberg. Making Sense of Recommendations. Journal of Behavioral Decision Making, 2019.

  M. Raghu, K. Blumer, G. Corrado, J. Kleinberg, Z. Obermeyer, S. Mullainathan. The Algorithmic Automation Problem: Prediction, Triage, and Human Effort. Machine Learning for Health (ML4H), 2018.

  J. Kleinberg, H. Lakkaraju, J. Leskovec, J. Ludwig, S. Mullainathan. Human Decisions and Machine Predictions. Quarterly Journal of Economics (QJE) volume 133:1, February 2018. Also appears as NBER Working Paper Number 23180, February 2017.

  H. Lakkaraju, J. Kleinberg, J. Leskovec, J. Ludwig, S. Mullainathan. The Selective Labels Problem: Evaluating Algorithmic Predictions in the Presence of Unobservables. Proc. 23rd ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2017.

  J. Kleinberg, A. Liang, S. Mullainathan. The Theory is Predictive, but is it Complete? An Application to Human Perception of Randomness. Proc. 18th ACM Conference on Economics and Computation (EC), 2017.

  J. Kleinberg, J. Ludwig, S. Mullainathan. A Guide to Solving Social Problems with Machine Learning. Harvard Business Review, December 2016.

  M. Luca, J. Kleinberg, S. Mullainathan. Algorithms Need Managers, Too. Harvard Business Review, 94:1(Jan/Feb 2016).

  A. Anderson, J. Kleinberg, S. Mullainathan. Assessing Human Error Against a Benchmark of Perfection. Proc. 22nd ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2016.

  J. Kleinberg, J. Ludwig, S. Mullainathan, Z. Obermeyer. Prediction Policy Problems. American Economic Review: Papers and Proceedings 105:5(2015).

  H. Lakkaraju, J. Leskovec, J. Kleinberg, S. Mullainathan. A Bayesian Framework for Modeling Human Evaluations. Proc. 15th SIAM International Conference on Data Mining (SDM), 2015.

  J. Kleinberg, S. Mullainathan. We Built Them, But We Don't Understand Them. In What to Think About Machines That Think: Today's Leading Thinkers on the Age of Machine Intelligence. Harper Perennial 2015.

Algorithms for Societal Decision-Making

• K. Donahue, J. Kleinberg. Fairness in model-sharing games. Proc. 32nd International World Wide Web Conference, 2023.
• B. Laufer, J. Kleinberg, K. Levy, H. Nissenbaum. Strategic Evaluation: Subjects, Evaluators, and Society. Proc. 3rd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO), 2023.
• B. Laufer, S. Jain, A.F. Cooper, J. Kleinberg, H. Heidari. Four Years of FAccT: A Reflexive, Mixed-Methods Analysis of Research Contributions, Shortcomings, and Future Prospects. Proc. ACM Conference on Fairness, Accountability, and Transparency (FAccT), 2022.
• J. Kleinberg, M. Raghavan. Algorithmic Monoculture and Social Welfare. Proc. National Academy of Sciences, 118(22), 1 June 2021.
• H. Heidari, S. Barocas, J. Kleinberg, K. Levy. On Modeling Human Perceptions of Allocation Policies with Uncertain Outcomes. Proc. 22nd ACM Conference on Economics and Computation (EC), 2021.
• H. Heidari, J. Kleinberg. Allocating Opportunities in a Dynamic Model of Intergenerational Mobility. Proc. ACM Conference on Fairness, Accountability, and Transparency (FAccT), 2021.
• K. Donahue, J. Kleinberg. Model-sharing Games: Analyzing Federated Learning Under Voluntary Participation. Proc. 35th AAAI Conference on Artificial Intelligence (AAAI-21), 2021.
• K. Donahue, J. Kleinberg. Optimality and Stability in Federated Learning: A Game-theoretic Approach. Advances in Neural Information Processing Systems (NeurIPS) 35, 2021.
• R. Abebe, J. Kleinberg, M. Weinberg. Subsidy Allocations in the Presence of Income Shocks. Proc. 34th AAAI Conference on Artificial Intelligence (AAAI-20), 2020.
• R. Abebe, S. Barocas, J. Kleinberg, K. Levy, M. Raghavan, D. Robinson. Roles for Computing in Social Change. Proc. ACM Conference on Fairness, Accountability, and Transparency (FAT*), 2020.
• K. Donahue, J. Kleinberg. Fairness and Utilization in Allocating Resources with Uncertain Demand. Proc. ACM Conference on Fairness, Accountability, and Transparency (FAT*), 2020.
• M. Raghavan, S. Barocas, J. Kleinberg, K. Levy Mitigating Bias in Algorithmic Employment Screening: Evaluating Claims and Practices. Proc. ACM Conference on Fairness, Accountability, and Transparency (FAT*), 2020.
• J. Kleinberg, J. Ludwig, S. Mullainathan, C. Sunstein. Algorithms as discrimination detectors. Proc. National Academy of Sciences, 117(48) 30096-30100, 1 December 2020.
• A. Rambachan, J. Kleinberg, J. Ludwig, S. Mullainathan. An Economic Approach to Regulating Algorithms. NBER Working Paper Number 27111, May 2020.
• J. Kleinberg, J. Ludwig, S. Mullainathan, C. Sunstein. Discrimination in the Age of Algorithms. Journal of Legal Analysis, 2019. Also appears as NBER Working Paper Number 25548, February 2019.
• J. Kleinberg, S. Mullainathan. Simplicity Creates Inequity: Implications for Fairness, Stereotypes, and Interpretability. Proc. 20th ACM Conference on Economics and Computation (EC), 2019.
• J. Kleinberg, M. Raghavan. Selection Problems in the Presence of Implicit Bias. Proc. 9th Conf. on Innovations in Theoretical Computer Science (ITCS), 2018.
• J. Kleinberg, J. Ludwig, S. Mullainathan, A. Rambachan. Algorithmic Fairness. AEA Papers and Proceedings 108:22-27, 2018.
• R. Abebe, J. Kleinberg, D. Parkes. Fair Division via Social Comparison. Proc. 16th Intl. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), 2017 .
• G. Pleiss, M. Raghavan, F. Wu, J. Kleinberg, K. Weinberger. On Fairness and Calibration. Advances in Neural Information Processing Systems 31, 2017.
• J. Kleinberg, S. Mullainathan, M. Raghavan. Inherent Trade-Offs in the Fair Determination of Risk Scores. Proc. 8th Conf. on Innovations in Theoretical Computer Science (ITCS), 2017.
• J. Kleinberg, M. Raghu. Team Performance with Test Scores. Proc. 16th ACM Conference on Economics and Computation (EC), 2015.
• J. Kleinberg, S. Oren. Mechanisms for (Mis)Allocating Scientific Credit. Proc. 43rd ACM Symposium on Theory of Computing, 2011.

Network Structure and Network Evolution

• N. Veldt, A. Benson, J. Kleinberg. Combinatorial characterizations and impossibilities for higher-order homophily. Science Advances, 9(1), 2023.
• A. Evtushenko, J. Kleinberg. Node-based Generalized Friendship Paradox fails. Scientific Reports 13(2074), 2023.
• R. Abebe, N. Immorlica, J. Kleinberg, B. Lucier, A. Shirali. On the Effect of Triadic Closure on Network Segregation. Proc. 23rd ACM Conference on Economics and Computation (EC), 2022.
• M. Papachristou, J. Kleinberg. Core-periphery Models for Hypergraphs. Proc. 28th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2022.
• N. Veldt, A. Benson, J. Kleinberg. Hypergraph Cuts with General Splitting Functions. SIAM Review, 2022.
• K. Van Koevering, A. Benson, J. Kleinberg. Random Graphs with Prescribed k-Core Sequences: A New Null Model for Network Analysis. Proc. 30th International World Wide Web Conference, 2021.
• C. Comrie, J. Kleinberg. Hypergraph Ego-networks and Their Temporal Evolution. IEEE Intl. Conf. on Data Mining (ICDM), 2021.
• A. Evtushenko, J. Kleinberg. The paradox of second-order homophily in networks. Scientific Reports 11(13360), 2021.
• N. Veldt, A. Benson, J. Kleinberg. The Generalized Mean Densest Subgraph Problem. Proc. 27th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2021.
• N. Veldt, A. Benson, J. Kleinberg. Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components. Advances in Neural Information Processing Systems (NeurIPS) 35, 2021. (This paper is an adaptation for NeurIPS of an earlier unpublished arXiv manuscript titled Augmented Sparsifiers for Generalized Hypergraph Cuts.)
• I. Amburg, J. Kleinberg, A. Benson. Planted Hitting Set Recovery in Hypergraphs. Journal of Physics: Complexity (Special Issue on Higher-Order Structures in Networks and Network Dynamical Systems), 2021.
• N. Veldt, A. Benson, J. Kleinberg. Localized Flow-Based Clustering in Hypergraphs. Proc. 26th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2020.
• A. Benson, J. Kleinberg. Core-fringe link prediction. Proc. 28th International World Wide Web Conference, 2019. See also the code and data accompanying the paper.
• A. Benson, R. Abebe, M. Schaub, A. Jadbabaie, J. Kleinberg. Simplicial Closure and Higher-order Link Prediction. Proc. National Academy of Sciences, 115(48) E11221-E11230, 27 November 2018. See also links for code and data accompanying the paper.
• A. Benson, J. Kleinberg. Found Graph Data and Planted Vertex Covers. Advances in Neural Information Processing Systems 32, 2018. See also links for code and data accompanying the paper.
• I. Kloumann, J. Ugander, J. Kleinberg. Block Models and Personalized PageRank. Proc. National Academy of Sciences, 114(1) 33-38, 3 January 2017.
• R. Rotabi, K. Kamath, J. Kleinberg, A. Sharma. Detecting Strong Ties Using Network Motifs. Proc. 26th International World Wide Web Conference, 2017.
• L. Backstrom, J. Kleinberg. Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook. Proc. 17th ACM Conference on Computer Supported Cooperative Work and Social Computing (CSCW), 2014.
• I. Kloumann, J. Kleinberg. Community membership identification from small seed sets. Proc. 20th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2014.
• J. Ugander, L. Backstrom, J. Kleinberg. Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections. Proc. 22nd International World Wide Web Conference, 2013.
  • See also the companion Web page by Johan Ugander, including R code.

  J. Ugander, B. Karrer, L. Backstrom, J. Kleinberg. Graph cluster randomization: network exposure to multiple universes. Proc. 19th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2013.

  J. Tang, T. Lou, J. Kleinberg. Inferring Social Ties across Heterogenous Networks. Proc. 5th ACM Conference on Web Search and Data Mining, 2012.

  L. Backstrom, J. Kleinberg. Network Bucket Testing. Proc. 20th International World Wide Web Conference, 2011.

  L. Backstrom, E. Bakshy, J. Kleinberg, T. Lento, I. Rosenn. Center of Attention: How Facebook Users Allocate Attention across Friends. Proc. 5th International AAAI Conference on Weblogs and Social Media, 2011.

  D. Romero, B. Meeder, V. Barash, J. Kleinberg. Maintaining Ties on Social Media Sites: The Competing Effects of Balance, Exchange, and Betweenness. Proc. 5th International AAAI Conference on Weblogs and Social Media, 2011.

  J. Cheng, D. Romero, B. Meeder, J. Kleinberg. Predicting Reciprocity in Social Networks. Proc. 3rd IEEE Conference on Social Computing, 2011.

  D. Romero, J. Kleinberg. The Directed Closure Process in Hybrid Social-Information Networks, with an Analysis of Link Formation on Twitter. Proc. 4th International AAAI Conference on Weblogs and Social Media, 2010.

  S. Arbesman, J. Kleinberg, S. Strogatz. Superlinear Scaling for Innovation in Cities. Physical Review E 79(1), 2009.

  J. Kleinberg, S. Suri, E. Tardos, T. Wexler. Strategic Network Formation with Structural Holes. Proc. 9th ACM Conference on Electronic Commerce, 2008.

  J. Leskovec, J. Kleinberg, C. Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. Proc. 11th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2005.

  R. Kleinberg, J. Kleinberg, Isomorphism and Embedding Problems for Infinite Limits of Scale-Free Graphs. Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, 2005.

  D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks. Proc. 12th International Conference on Information and Knowledge Management (CIKM), 2003.

  D. Callaway, J. Hopcroft, J. Kleinberg, M. Newman, S. Strogatz. Are randomly grown graphs really random? Physical Review E 64, 041902 (2001).

Information Flow and Dynamic Behavior in Networks

• Y. Wang, J. Kleinberg. On the Relationship Between Relevance and Conflict in Online Social Link Recommendations. Advances in Neural Information Processing Systems (NeurIPS) 37, 2023.
• M. Meister, J. Kleinberg. Optimizing the order of actions in contact tracing. PNAS Nexus, January 2023.
• M. Papachristou, S. Banerjee, J. Kleinberg. Dynamic Interventions for Networked Contagions. Proc. 32nd International World Wide Web Conference, 2023.
• M. Papachristou, J. Kleinberg. Allocating Stimulus Checks in Times of Crisis. Proc. 31st International World Wide Web Conference, 2022.
• R. Abebe, T-H Chan, J. Kleinberg, Z. Liang, D. Parkes, M. Sozio, C. Tsourakakis. Opinion Dynamics with Varying Susceptibility to Persuasion via Non-Convex Local Search. ACM Transactions on Knowledge Discovery from Data, 2022.
• K. Van Koevering, Y. Hong, J. Kleinberg. Exporting Geography Into A Virtual Landscape: A Global Pandemic Locally Discussed. arXiv/2210.07187, 2022.
• J. Gaitonde, J. Kleinberg, E. Tardos. Polarization in Geometric Opinion Dynamics. Proc. 22nd ACM Conference on Economics and Computation (EC), 2021.
• J. Gaitonde, J. Kleinberg, E. Tardos. Adversarial Perturbations of Opinion Dynamics in Networks. Proc. 21st ACM Conference on Economics and Computation (EC), 2020.
• R. Abebe, L. Adamic, J. Kleinberg. Mitigating Overexposure in Viral Marketing. Proc. 32nd AAAI Conference on Artificial Intelligence (AAAI-18), 2018.
• M. Raghavan, A. Anderson, J. Kleinberg. Mapping the Invocation Structure of Online Political Interaction. Proc. 27th International World Wide Web Conference, 2018.
• R. Abebe, J. Kleinberg, D. Parkes, C. Tsourakakis. Opinion Dynamics with Varying Susceptibility to Persuasion. Proc. 24th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2018. This KDD 2018 version of the paper has been superseded by an updated version that merges the KDD 2018 paper with a WWW 2019 paper of Chan, Liang, and Sozio.
• J. Cheng, J. Kleinberg, J. Leskovec, D. Liben-Nowell, B. State, K. Subbian, L. Adamic. Do Diffusion Protocols Govern Cascade Growth? Proc. 12th International AAAI Conference on Weblogs and Social Media (ICWSM), 2018.
• R. Rotabi, C. Danescu-Niculescu-Mizil, J. Kleinberg. Tracing the Use of Practices through Networks of Collaboration. Proc. 11th International AAAI Conference on Weblogs and Social Media (ICWSM), 2017.
• R. Rotabi, C. Danescu-Niculescu-Mizil, J. Kleinberg. Competition and Selection Among Conventions. Proc. 26th International World Wide Web Conference, 2017.
• R. Rotabi, K. Kamath, J. Kleinberg, A. Sharma. Cascades: A view from Audience. Proc. 26th International World Wide Web Conference, 2017.
• D. Romero, B. Uzzi, J. Kleinberg. Social Networks Under Stress. Proc. 25th International World Wide Web Conference, 2016.
• J. Cheng, L. Adamic, J. Kleinberg, J. Leskovec. Do Cascades Recur?. Proc. 25th International World Wide Web Conference, 2016.
• R. Rotabi, J. Kleinberg. The Status Gradient of Trends in Social Media. Proc. 10th International AAAI Conference on Weblogs and Social Media, 2016.
• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Global Diffusion via Cascading Invitations: Structure, Growth, and Homophily. Proc. 24th International World Wide Web Conference, 2015.
• I. Kloumann, L. Adamic, J. Kleinberg, S. Wu. The Lifecycles of Apps in a Social Ecosystem. Proc. 24th International World Wide Web Conference, 2015.
• J. Cheng, L. Adamic, A. Dow, J. Kleinberg, J. Leskovec. Can Cascades Be Predicted? Proc. 23rd International World Wide Web Conference, 2014.
  • See also the Facebook Data Science blog post about this work.

  L. Backstrom, J. Kleinberg, L. Lee, C. Danescu-Niculescu-Mizil. Characterizing and Curating Conversation Threads: Expansion, Focus, Volume, Re-entry. Proc. 6th ACM Conference on Web Search and Data Mining, 2013.

  F. Chierichetti, J. Kleinberg, S. Oren. On discrete preferences and coordination. Proc. 14th ACM Conference on Electronic Commerce, 2013.

  D. Kempe, J. Kleinberg, S. Oren, A. Slivkins. Selection and Influence in Cultural Dynamics. Proc. 14th ACM Conference on Electronic Commerce, 2013.

  J. Ugander, L. Backstrom, C. Marlow, J. Kleinberg. Structural Diversity in Social Contagion. Proc. National Academy of Sciences, 109(16) 5962-5966, 17 April 2012.

  K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, A. Sharma. Preventing Unraveling in Social Networks: The Anchored k-Core Problem, Proc. 39th International Colloquium on Automata, Languages and Programming (ICALP), 2012.

  F. Chierichetti, J. Kleinberg, A. Panconesi. How to schedule a cascade in an arbitrary graph. Proc. 13th ACM Conference on Electronic Commerce, 2012.

  L. Blume, D. Easley, J. Kleinberg, R. Kleinberg, E. Tardos. Which Networks Are Least Susceptible to Cascading Failures? Proc. 52nd IEEE Symposium on Foundations of Computer Science, 2011.

  L. Blume, D. Easley, J. Kleinberg, R. Kleinberg, E. Tardos. Network Formation in the Presence of Contagious Risk. Proc. 12th ACM Conference on Electronic Commerce, 2011.

  F. Chierichetti, J. Kleinberg, D. Liben-Nowell. Reconstructing Patterns of Information Diffusion from Incomplete Observations. Advances in Neural Information Processing Systems 24, 2011.

  D. Romero, B. Meeder, J. Kleinberg. Differences in the Mechanics of Information Diffusion Across Topics: Idioms, Political Hashtags, and Complex Contagion on Twitter. Proc. 20th International World Wide Web Conference, 2011.

  S. Wu, C. Tan, J. Kleinberg, M. Macy. Does Bad News Go Away Faster? Proc. 5th International AAAI Conference on Weblogs and Social Media, 2011.

  D. Cosley, D. Huttenlocher, J. Kleinberg, X. Lan, S. Suri. Sequential Influence Models in Social Networks. Proc. 4th International AAAI Conference on Weblogs and Social Media, 2010.

  D. Liben-Nowell, J. Kleinberg. Tracing Information Flow on a Global Scale Using Internet Chain-Letter Data. Proc. National Academy of Sciences, 105(12):4633–4638, 25 March 2008.

  • We are interested in gathering additional data about the spread of the chain-letter petitions described in this paper. Please visit http://petitions.cs.cornell.edu or http://petitions.cs.carleton.edu to learn more or to help.

  G. Kossinets, J. Kleinberg, D. Watts. The Structure of Information Pathways in a Social Communication Network. Proc. 14th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2008.

  D. Crandall, D. Cosley, D. Huttenlocher, J. Kleinberg, S. Suri. Feedback Effects between Similarity and Social Influence in Online Communities. Proc. 14th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2008.

  J. Kleinberg. Cascading Behavior in Networks: Algorithmic and Economic Issues. In Algorithmic Game Theory (N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani, eds.), Cambridge University Press, 2007.

  J. Kleinberg The Wireless Epidemic. Nature (News and Views) 449(2007), 287-288.

  N. Immorlica, J. Kleinberg, M. Mahdian, T. Wexler. The Role of Compatibility in the Diffusion of Technologies Through Social Networks. Proc. 8th ACM Conference on Electronic Commerce, 2007.

  L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group Formation in Large Social Networks: Membership, Growth, and Evolution. Proc. 12th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2006.

  J. Leskovec, A. Singh, J. Kleinberg. Patterns of Influence in a Recommendation Network. Proc. Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2006.

  D. Kempe, J. Kleinberg, E. Tardos. Influential Nodes in a Diffusion Model for Social Networks. Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP), 2005.

  D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2003.

Incentives and Game-Theoretic Analysis

• K. Tomlinson, J. Ugander, J. Kleinberg. Ballot length in instant runoff voting. Proc. 37th AAAI Conference on Artificial Intelligence (AAAI-23), 2023.
• H. Heidari, S. Barocas, J. Kleinberg, K. Levy. Informational Diversity and Affinity Bias in Team Growth Dynamics. Proc. 3rd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO), 2023.
• J. Kleinberg, R. Kleinberg, S. Oren. Optimal Stopping with Behaviorally Biased Agents: The Role of Loss Aversion and Changing Reference Points. Proc. 22nd ACM Conference on Economics and Computation (EC), 2021.
• J. Kleinberg, S. Oren, M. Raghavan, N. Sklar. Stochastic Model for Sunk Cost Bias. Proc. 37th Conference on Uncertainty in Artificial Intelligence (UAI), 2021.
• J. Kleinberg, M. Raghavan. How Do Classifiers Induce Agents To Invest Effort Strategically? Proc. 20th ACM Conference on Economics and Computation (EC), 2019.
• J. Kleinberg, R. Kleinberg. Delegated Search Approximates Efficient Search. Proc. 19th ACM Conference on Economics and Computation (EC), 2018.
• J. Kleinberg, S. Oren, M. Raghavan. Planning with Multiple Biases. Proc. 18th ACM Conference on Economics and Computation (EC), 2017.
• J. Kleinberg, S. Mullainathan, J. Ugander. Comparison-Based Choices. Proc. 18th ACM Conference on Economics and Computation (EC), 2017.
• J. Kleinberg, S. Oren, M. Raghavan. Planning Problems for Sophisticated Agents with Present Bias. Proc. 17th ACM Conference on Economics and Computation (EC), 2016.
• J. Kleinberg, S. Oren. Dynamic Models of Reputation and Competition in Job-Market Matching. Proc. 6th Conference on Innovations in Theoretical Computer Science (ITCS), 2015.
• L. Blume, D. Easley, J. Kleinberg, R. Kleinberg, E. Tardos. Introduction to computer science and economic theory. Journal of Economic Theory 156(2015).
• J. Kleinberg, S. Oren. Time-Inconsistent Planning: A Computational Problem in Behavioral Economics. Proc. 15th ACM Conference on Economics and Computation (EC), 2014.
• P. Frazier, D. Kempe, J. Kleinberg, R. Kleinberg. Incentivizing Exploration. Proc. 15th ACM Conference on Economics and Computation (EC), 2014.
• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Steering User Behavior with Badges. Proc. 22nd International World Wide Web Conference, 2013.
• J. Kleinberg, K. Ligett. Information-sharing in social networks. Games and Economic Behavior 82, 2013.
• F. Chierichetti, J. Kleinberg. Voting with Limited Information and Many Alternatives. Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, 2012.
• J. Kleinberg, E. Tardos. Balanced Outcomes in Social Exchange Networks. Proc. 40th ACM Symposium on Theory of Computing, 2008.
• L. Blume, D. Easley, J. Kleinberg, E. Tardos. Trading Networks with Price-Setting Agents. Proc. 8th ACM Conference on Electronic Commerce, 2007.
• J. Kleinberg, P. Raghavan. Query Incentive Networks. Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.
• E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, T. Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation. Proc. 45th IEEE Symposium on Foundations of Computer Science, 2004.

Representations for Learning

• E. Abbe, S. Bengio, E. Cornacchia, J. Kleinberg, A. Lotfi, M. Raghu, C. Zhang. Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures. Advances in Neural Information Processing Systems (NeurIPS) 36, 2022.
• C. Zhang, M. Raghu, J. Kleinberg, S. Bengio. Pointer Value Retrieval: A new benchmark for understanding the limits of neural network generalization. arXiv/2107.12580, 2021.
• K. Blumer, S. Venugopalan, M. Brenner, J. Kleinberg. Using a Cross-Task Grid of Linear Probes to Interpret CNN Model Predictions On Retinal Images. ICML Workshop on Interpretable Machine Learning in Healthcare, 2021.
• M. Raghu, C. Zhang, J. Kleinberg, S. Bengio. Transfusion: Understanding Transfer Learning with Applications to Medical Imaging. Advances in Neural Information Processing Systems 33, 2019.
• M. Raghu, A. Irpan, J. Andreas, R. Kleinberg, Q.V. Le, J. Kleinberg. Can Deep Reinforcement Learning Solve Erdos-Selfridge-Spencer Games? Proc. 35th Intl. Conf. on Machine Learning (ICML), 2018.
• M. Raghu, B. Poole, J. Kleinberg, S. Ganguli, J. Sohl-Dickstein. On the expressive power of deep neural networks. Proc. 34th Intl. Conf. on Machine Learning (ICML), 2017.

Language, Text Content, and Social Interaction

• K. Van Koevering, A. Benson, J. Kleinberg. Frozen Binomials on the Web: Word Ordering and Language Conventions in Online Text. Proc. 29th International World Wide Web Conference, 2020.
• C. Danescu-Niculescu-Mizil, J. Cheng, J. Kleinberg, L. Lee. You had me at hello: How phrasing affects memorability. Proc. 50th Annual Meeting of the Association for Computational Linguistics, 2012.
• C. Danescu-Niculescu-Mizil, L. Lee, B. Pang, J. Kleinberg. Echoes of power: Language effects and power differences in social interaction. Proc. 21st International World Wide Web Conference, 2012.

General Articles on Web Information and On-Line Social Networks

• J. Hofman, D. Watts, S. Athey, F. Garip, T. Griffiths, J. Kleinberg, H. Margetts, S. Mullainathan, M. Salganik, S. Vazire, A. Vespignani, T. Yarkoni. Integrating explanation and prediction in computational social science. Nature 595(2021).
• J. Kleinberg. How can we have this much data and still not understand collective human behavior? In What's the question about your field that you dread being asked?, 2013.
• J. Kleinberg. E Pluribus Unum. In This Will Make You Smarter: New Scientific Concepts to Improve Your Thinking. Harper Perennial 2012.
• J. Kleinberg. The Human Texture of Information. In Is the Internet Changing the Way You Think? Harper Perennial 2011.
• J. Kleinberg. What Can Huge Datasets Teach Us About Society and Ourselves? In Future Science, Vintage 2011.
• J. Kleinberg. The convergence of social and technological networks. Communications of the ACM, 51(11):66-72, 2008.
• J. Kleinberg, S. Lawrence. The Structure of the Web. Science 294(2001), 1849. This version also appears in the on-line edition of Science.
• J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. The Web as a graph: Measurements, models and methods. Invited survey at the International Conference on Combinatorics and Computing, 1999.

General Articles on Algorithms, Complexity, and Discrete Math

• J. Kleinberg. Foreword to Behind Deep Blue, by Feng-Hsiung Hsu. Princeton Univ. Press, 25th anniversary edition, 2022. See also Princeton University Press's page for the book.
• J. Kleinberg. Digital Representation. In This Idea Is Brilliant: Lost, Overlooked, and Underappreciated Scientific Concepts Everyone Should Know. Harper Perennial 2018.
• J. Kleinberg. The Pigeonhole Principle. In This Explains Everything. Harper Perennial 2013.
• J. Kleinberg. The Mathematics of Algorithm Design. In Princeton Companion to Mathematics, (T. Gowers and J. Barrow-Green, eds.), Princeton Univ. Press, 2008.
• J. Kleinberg, C. Papadimitriou. Computability and Complexity. An essay in Computer Science: Reflections on the Field, Reflections from the Field. National Academies Press, 2004.

Opinion, Evaluation, and Polarization

• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Effects of User Similarity in Social Media. Proc. 5th ACM Conference on Web Search and Data Mining, 2012.
• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Discovering Value from Community Activity on Focused Question Answering Sites: A Case Study of Stack Overflow. Proc. 18th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2012.
• D. Bindel, J. Kleinberg, S. Oren. How Bad is Forming Your Own Opinion? Proc. 52nd IEEE Symposium on Foundations of Computer Science, 2011.
• S. Marvel, J. Kleinberg, R. Kleinberg, S. Strogatz. Continuous-Time Model of Structural Balance. Proc. National Academy of Sciences, 108(5) 1771-1776, 1 February 2011.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Governance in Social Media: A case study of the Wikipedia promotion process. Proc. 4th International AAAI Conference on Weblogs and Social Media, 2010.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Signed Networks in Social Media. Proc. 28th ACM SIGCHI Conference on Human Factors in Computing Systems (CHI), 2010.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Predicting Positive and Negative Links in Online Social Networks. Proc. 19th International World Wide Web Conference, 2010.
• S. Marvel, J. Kleinberg, S. Strogatz. The Energy Landscape of Social Balance. Physical Review Letters 103(19), 2009.
• C. Danescu-Niculescu-Mizil, G. Kossinets, J. Kleinberg, L. Lee. How Opinions are Received by Online Communities: A Case Study on Amazon.com Helpfulness Votes. Proc. 18th International World Wide Web Conference, 2009.

Temporal Analysis and Bursty Phenomena

• F. Chierichetti, J. Kleinberg, R. Kumar, M. Mahdian, S. Pandey. Event Detection via Communication Pattern Analysis. Proc. 8th International AAAI Conference on Weblogs and Social Media, 2014.
• J. Leskovec, L. Backstrom, J. Kleinberg. Meme-tracking and the dynamics of the news cycle. Proc. 15th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2009.
• L. Backstrom, J. Kleinberg, R. Kumar. Optimizing Web traffic via the Media Scheduling Problem. Proc. 15th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2009.
• J. Kleinberg. Temporal Dynamics of On-Line Information Streams. In Data Stream Management: Processing High-Speed Data Streams, (M. Garofalakis, J. Gehrke, R. Rastogi, eds.), Springer, 2004.
• J. Aizen, D. Huttenlocher, J. Kleinberg, A. Novak. Traffic-Based Feedback on the Web. Proceedings of the National Academy of Sciences 101(Suppl.1):5254-5260, 2004. (Also available in pre-print form.)
• J. Kleinberg. Bursty and Hierarchical Structure in Streams. Proc. 8th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2002.
  • See also some sample results from the burst detection algorithm described in this paper.

Team Formation and Dynamics

• I. Kloumann, C. Tan, J. Kleinberg, Lee. Internet Collaboration on Extremely Difficult Problems: Research versus Olympiad Questions on the Polymath Site. Proc. 25th International World Wide Web Conference, 2016.
• D. Romero, D. Huttenlocher, J. Kleinberg. Coordination and Efficiency in Decentralized Collaboration. Proc. 9th International AAAI Conference on Weblogs and Social Media, 2015.

Algorithms and Models for On-Line Education

• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Engaging with Massive Online Courses. Proc. 23rd International World Wide Web Conference, 2014.
• A. Ghosh, J. Kleinberg. Incentivizing participation in online forums for education. Proc. 14th ACM Conference on Electronic Commerce, 2013.
• T. Novikoff, J. Kleinberg, S. Strogatz. Education of a Model Student. Proc. National Academy of Sciences, 109(6) 1868-1873, 7 February 2012.

Privacy in Network Analysis and Data Mining

• D. Crandall, L. Backstrom, D. Cosley, S. Suri, D. Huttenlocher, J. Kleinberg. Inferring Social Ties from Geographic Coincidences. Proc. National Academy of Sciences 107(52) 22436-22441, 28 December 2010.
• L. Backstrom, C. Dwork, J. Kleinberg. Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and Structural Steganography. Proc. 16th Intl. World Wide Web Conference, 2007.
• J. Kleinberg, C. Papadimitriou, P. Raghavan. Auditing Boolean Attributes. Proc. 19th ACM Symposium on Principles of Database Systems, 2000.

Spatial Embeddings of Information

• D. Crandall, L. Backstrom, D. Huttenlocher, J. Kleinberg. Mapping the World's Photos. Proc. 18th International World Wide Web Conference, 2009.
  • See also some maps of cities and continents constructed using the methods in this paper.

  L. Backstrom, J. Kleinberg, R. Kumar, J. Novak. Spatial Variation in Search Engine Queries. Proc. 17th International World Wide Web Conference, 2008.

Gossip Algorithms in Networks

• D. Kempe, J. Kleinberg, A. Demers. Spatial gossip and resource location protocols. Proc. 33rd ACM Symposium on Theory of Computing, 2001. (In PDF.)
• D. Kempe, J. Kleinberg. Protocols and Impossibility Results for Gossip-Based Communication Mechanisms. Proc. 43rd IEEE Symposium on Foundations of Computer Science, 2002.

Clustering, Indexing, and Data Mining

• A. Dasgupta, J. Hopcroft, J. Kleinberg, M. Sandler. On Learning Mixtures of Heavy-Tailed Distributions. Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.
• J. Kleinberg, M. Sandler. Using Mixture Models for Collaborative Filtering. Proc. 36th ACM Symposium on Theory of Computing, 2004.
• J. Kleinberg, C. Papadimitriou, P. Raghavan. Segmentation problems. Journal of the ACM, 51(2), 2004.
• P. Felzenszwalb, D. Huttenlocher, J. Kleinberg. Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis. Advances in Neural Information Processing Systems 16, 2003. (In PDF.)
• J. Kleinberg, M. Sandler. Convergent Algorithms for Collaborative Filtering. Proc. 4th ACM Conference on Electronic Commerce, 2003. (In PDF.)
• J. Kleinberg. An Impossibility Theorem for Clustering. Advances in Neural Information Processing Systems 15, 2002.
• J. Kleinberg, C. Papadimitriou, P. Raghavan. On the Value of Private Information. Proc. 8th Conf. on Theoretical Aspects of Rationality and Knowledge, 2001.
• J. Kleinberg, E. Tardos. Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. Proc. 40th IEEE Symposium on Foundations of Computer Science, 1999.
• J. Kleinberg, C. Papadimitriou, P. Raghavan. A micro-economic view of data mining. Data Mining and Knowledge Discovery, 2(4), 1998.
• D. Gibson, J. Kleinberg, P. Raghavan. Clustering categorical data: An approach based on dynamical systems. Proc. 24th Intl. Conference on Very Large Databases, 1998.
• J. Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. Proc. 29th ACM Symposium on Theory of Computing, 1997.

Network Analysis, Management, and Routing

• A. Frieze, J. Kleinberg, R. Ravi, W. Debany. Line-of-Sight Networks. Proc. 18th ACM-SIAM Symposium on Discrete Algorithms, 2007.
• A. Krause, C. Guestrin, A. Gupta, J. Kleinberg. Near-optimal Sensor Placements: Maximizing Information while Minimizing Communication Cost. Proc. Information Processing in Sensor Networks (IPSN), 2006.
• J. Kleinberg. An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs. Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.
• I. Abraham, Y. Bartal, T-H. Chan, K. Dhamdhere, A. Gupta, J. Kleinberg, O. Neiman, A. Slivkins. Metric Embeddings with Relaxed Guarantees. Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.
• J. Kleinberg, A. Slivkins, T. Wexler. Triangulation and Embedding using Small Sets of Beacons. Proc. 45th IEEE Symposium on Foundations of Computer Science, 2004.
• J. Kleinberg, M. Sandler, A. Slivkins. Network Failure Detection and Graph Connectivity. Proc. 15th ACM-SIAM Symposium on Discrete Algorithms, 2004. (In PDF.)
• A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, B. Yener. Provisioning a virtual private network: A network design problem for multicommodity flow. Proc. 33rd ACM Symposium on Theory of Computing, 2001.
• J. Kleinberg. Detecting a Network Failure. Proc. 41st IEEE Symposium on Foundations of Computer Science, 2000.
• D. Kempe, J. Kleinberg, A. Kumar. Connectivity and inference problems for temporal networks. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
• R. Fagin, A. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld, M. Sudan, A. Tomkins. Random Walks with `Back Buttons.' Proc. 32nd ACM Symposium on Theory of Computing, 2000.
• A. Kumar, J. Kleinberg. Fairness measures for resource allocation. Proc. 41st IEEE Symposium on Foundations of Computer Science, 2000.
• J. Kleinberg, Y. Rabani, E. Tardos. Fairness in routing and load balancing. Proc. 40th IEEE Symposium on Foundations of Computer Science, 1999.
• J. Kleinberg, A. Kumar. Wavelength conversion in optical networks. Proc. 10th ACM-SIAM Symposium on Discrete Algorithms, 1999.
• M. Charikar, J. Kleinberg, S.R. Kumar, S. Rajagopalan, A. Sahai, A. Tomkins. Minimizing wirelength in zero and bounded skew clock trees. Proc. 10th ACM-SIAM Symposium on Discrete Algorithms, 1999.
• J. Kleinberg. Decision algorithms for unsplittable flow and the half-disjoint paths problem. Proc. 30th ACM Symposium on Theory of Computing, 1998.
• J. Kleinberg, Y. Rabani, E. Tardos. Allocating bandwidth for bursty connections. Proc. 29th ACM Symposium on Theory of Computing, 1997.
• J. Kleinberg. Single-source unsplittable flow. Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996.
• J. Kleinberg, R. Rubinfeld. Short paths in expander graphs. Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996.
• A. Aggarwal, J. Kleinberg, D. Williamson. Node-disjoint paths on the mesh, and a new trade-off in VLSI layout. Proc. 28th ACM Symposium on Theory of Computing, 1996.
• J. Kleinberg, E. Tardos. Disjoint paths in densely embedded graphs. Proc. 36th IEEE Symposium on Foundations of Computer Science, 1995.
• J. Kleinberg, E. Tardos. Approximations for the disjoint paths problem in high-diameter planar networks. Proc. 27th ACM Symposium on Theory of Computing, 1995.
• J. Kleinberg. Approximation Algorithms for Disjoint Paths Problems. Ph.D Thesis, Dept. of EECS, MIT, 1996.

Dynamic Network Algorithms and Adversarial Queueing Theory

• A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, D. Williamson. Adversarial queueing theory. Proc. 28th ACM Symposium on Theory of Computing, 1996.
• D.M. Andrews, B. Awerbuch, A. Fernandez, J. Kleinberg, F.T. Leighton, Z. Liu. Universal stability results for greedy contention-resolution protocols. Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996.
• E. Anshelevich, D. Kempe, J. Kleinberg. Stability of Load Balancing Algorithms in Dynamic Adversarial Systems. Proc. 34th ACM Symposium on Theory of Computing, 2002.

Comparative Genomics and Evolutionary Models

• L. Meyerguz, J. Kleinberg, R. Elber. The network of sequence flow between protein structures. Proceedings of the National Academy of Sciences 10.1073, 27 June 2007.
• L. Meyerguz, D. Kempe, J. Kleinberg, R. Elber. The Evolutionary Capacity of Protein Structures. Proc. ACM RECOMB Intl. Conference on Computational Molecular Biology, 2004.
• I. V. Yap, D. Schneider, J. Kleinberg, D. Matthews, S. Cartinhour, S. R. McCouch. A Graph-Theoretic Approach to Comparing and Integrating Genetic, Physical and Sequence-Based Maps. Genetics, Vol. 165(2003).
• D. Goldberg, S. McCouch, J. Kleinberg. Constructing comparative maps with unresolved marker order. Proc. Pacific Symposium on Biocomputing, 2002.
• D. Goldberg, S. McCouch, J. Kleinberg. Algorithms for Constructing Comparative Maps. Conference on Gene Order Dynamics, Comparative Maps, and Multigene Families, 2000. (In PDF.)
• J. Kleinberg, D. Liben-Nowell. The Syntenic Diameter of the Space of N-Chromosome Genomes. Conference on Gene Order Dynamics, Comparative Maps, and Multigene Families, 2000.
• J. Kleinberg. Efficient Algorithms for Protein Sequence Design and the Analysis of Certain Evolutionary Fitness Landscapes. Proc. 3rd ACM RECOMB Intl. Conference on Computational Molecular Biology, 1999.

Protein Structure Analysis

• L.P. Chew, D. Huttenlocher, K. Kedem, J. Kleinberg. Fast Detection of Common Geometric Substructure in Proteins. Proc. 3rd ACM RECOMB Intl. Conference on Computational Molecular Biology, 1999.
• B. Berger, J. Kleinberg, F.T. Leighton. Reconstructing a Three-Dimensional Model with Arbitrary Errors. Proc. 28th ACM Symposium on Theory of Computing, 1996.

Algorithms for NP-hard problems

• E. Dantsin, A. Goerdt, E. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schoning, A deterministic algorithm for satisfiability based on local search. Theoretical Computer Science, 289(2002).
• J. Kleinberg, M. Goemans. The Lovasz theta function and a semi-definite programming relaxation of vertex cover. SIAM J. Discrete Math, 11(1998).
• M. Goemans, J. Kleinberg. An improved approximation ratio for the minimum latency problem. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, 1996.

Fault-tolerance in Distributed Computing

• J. Kleinberg, H. Attiya, N. Lynch. Trade-offs between message delivery and quiesce times in connection management protocols. Proc. 3rd Israel Symposium on Theory of Computing and Systems, 1995.
• J. Kleinberg, S. Mullainathan. Resource bounds and combinations of consensus objects. Proc. 12th ACM Symposium on Principles of Distributed Computing, 1993.

Geometric Pattern Matching

• D. Huttenlocher, J. Kleinberg. Comparing point sets under projection. Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, 1994.
• D. Huttenlocher, K. Kedem, J. Kleinberg. On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane. Proc. 8th ACM Symposium on Computational Geometry, 1992.

On-Line Algorithms

• M. Charikar, R. Fagin, V. Guruswami, J. Kleinberg, P. Raghavan, A. Sahai. Query strategies for priced information. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
• J. Kleinberg, R. Motwani, P. Raghavan, S. Venkatasubramanian. Storage management for evolving databases. Proc. 38th IEEE Symposium on Foundations of Computer Science, 1997.
• R. El-Yaniv, J. Kleinberg. Geometric two-server algorithms. Information Processing Letters 53(1995).
• J. Kleinberg. The localization problem for mobile robots. Proc. 35th IEEE Symposium on Foundations of Computer Science, 1994.
• J. Kleinberg. On-line search in a simple polygon. Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, 1994.
• J. Kleinberg. A lower bound for two-server balancing algorithms. Information Processing Letters 51(1994).

Contact Information