Publications

2024

• 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.

2023

• K. Donahue, J. Kleinberg. Fairness in model-sharing games. Proc. 32nd International World Wide Web Conference, 2023.
• M. Papachristou, S. Banerjee, J. Kleinberg. Dynamic Interventions for Networked Contagions. Proc. 32nd International World Wide Web Conference, 2023.
• 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.
• 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.
• 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.
• 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.
• 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.
• K. Donahue, J. Kleinberg. Private Blotto: Viewpoint Competition with Polarized Agents. arXiv/2302.14123, 2023.
• E. Pierson, D. Shanmugam, R. Movva, J. Kleinberg, M. Agrawal, M. Dredze, K. Ferryman, J.W. Gichoya, D. Jurafsky, P.W. Koh, K. Levy, S. Mullainathan, Z. Obermeyer, H. Suresh, K. Vafa. Use large language models to promote equity. arXiv/2312.14804, 2023.

2022

• 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.
• 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.
• 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.
• M. Papachristou, J. Kleinberg. Allocating Stimulus Checks in Times of Crisis. Proc. 31st International World Wide Web Conference, 2022.
• M. Papachristou, J. Kleinberg. Core-periphery Models for Hypergraphs. Proc. 28th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2022.
• 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.
• 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.
• 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.
• D. Fudenberg, J. Kleinberg, A. Liang, S. Mullainathan. Measuring the Completeness of Economic Models. Journal of Political Economy, 2022.
• N. Veldt, A. Benson, J. Kleinberg. Hypergraph Cuts with General Splitting Functions. SIAM Review, 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.
• J. Kleinberg, E. Ryu, E. Tardos. Ordered Submodularity and its Applications to Diversifying Recommendations. arXiv/2203.00233, 2022.
• K. Van Koevering, Y. Hong, J. Kleinberg. Exporting Geography Into A Virtual Landscape: A Global Pandemic Locally Discussed. arXiv/2210.07187, 2022.

2021

• H. Heidari, J. Kleinberg. Allocating Opportunities in a Dynamic Model of Intergenerational Mobility. Proc. ACM Conference on Fairness, Accountability, and Transparency (FAccT), 2021.
• J. Kleinberg, M. Raghavan. Algorithmic Monoculture and Social Welfare. Proc. National Academy of Sciences, 118(22), 1 June 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. 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.
• 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.)
• 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.
• J. Gaitonde, J. Kleinberg, E. Tardos. Polarization in Geometric Opinion Dynamics. Proc. 22nd ACM Conference on Economics and Computation (EC), 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.
• 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.
• K. Donahue, J. Kleinberg. Model-sharing Games: Analyzing Federated Learning Under Voluntary Participation. Proc. 35th AAAI Conference on Artificial Intelligence (AAAI-21), 2021.
• 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.
• J. Kleinberg, S. Oren, M. Raghavan, N. Sklar. Stochastic Model for Sunk Cost Bias. Proc. 37th Conference on Uncertainty in Artificial Intelligence (UAI), 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.
• 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.
• 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.
• 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).
• 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.

2020

• 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 (FAccT), 2020.
• K. Donahue, J. Kleinberg. Fairness and Utilization in Allocating Resources with Uncertain Demand. Proc. ACM Conference on Fairness, Accountability, and Transparency (FAccT), 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 (FAccT), 2020.
• 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.
• J. Gaitonde, J. Kleinberg, E. Tardos. Adversarial Perturbations of Opinion Dynamics in Networks. Proc. 21st ACM Conference on Economics and Computation (EC), 2020.
• 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.

  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.

  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.

2019

• M. Raghu, C. Zhang, J. Kleinberg, S. Bengio. Transfusion: Understanding Transfer Learning with Applications to Medical Imaging. Advances in Neural Information Processing Systems (NeurIPS) 33, 2019.
• 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.
• 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. How Do Classifiers Induce Agents To Invest Effort Strategically? Proc. 20th ACM Conference on Economics and Computation (EC), 2019.
• 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.
• M. Yeomans, A. Shah., S. Mullainathan, J. Kleinberg. Making Sense of Recommendations. Journal of Behavioral Decision Making, 2019.

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.
• J. Kleinberg, J. Ludwig, S. Mullainathan, C. Sunstein. Discrimination in the Age of Algorithms. Journal of Legal Analysis, 2018. Also appears as NBER Working Paper Number 25548, February 2019.
• 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.
• J. Kleinberg, R. Kleinberg. Delegated Search Approximates Efficient Search. Proc. 19th ACM Conference on Economics and Computation (EC), 2018.
• 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, L. Adamic, J. Kleinberg. Mitigating Overexposure in Viral Marketing. Proc. 32nd AAAI Conference on Artificial Intelligence (AAAI-18), 2018.
• 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, 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.
• 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 in ACM Transactions on Knowledge Discovery from Data 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.
• J. Kleinberg. Digital Representation. In This Idea Is Brilliant: Lost, Overlooked, and Underappreciated Scientific Concepts Everyone Should Know. Harper Perennial 2018.

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.
• G. Pleiss, M. Raghavan, F. Wu, J. Kleinberg, K. Weinberger. On Fairness and Calibration. Advances in Neural Information Processing Systems 31, 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, S. Mullainathan, J. Ugander. Comparison-Based Choices. Proc. 18th ACM Conference on Economics and Computation (EC), 2017.
• J. Kleinberg, S. Oren, M. Raghavan. Planning with Multiple Biases. Proc. 18th ACM Conference on Economics and Computation (EC), 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.
• 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.
• 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.
• R. Rotabi, K. Kamath, J. Kleinberg, A. Sharma. Detecting Strong Ties Using Network Motifs. Proc. 26th International World Wide Web Conference, 2017.
• R. Abebe, J. Kleinberg, D. Parkes. Fair Division via Social Comparison. Proc. 16th Intl. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), 2017.
• I. Kloumann, J. Ugander, J. Kleinberg. Block Models and Personalized PageRank. Proc. National Academy of Sciences, 114(1) 33-38, 3 January 2017.

2016

• 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.
• 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.
• 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, S. Oren, M. Raghavan. Planning Problems for Sophisticated Agents with Present Bias. Proc. 17th ACM Conference on Economics and Computation (EC), 2016.
• R. Rotabi, J. Kleinberg. The Status Gradient of Trends in Social Media. Proc. 10th International AAAI Conference on Weblogs and Social Media, 2016.
• 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).

2015

• J. Kleinberg, M. Raghu. Team Performance with Test Scores. Proc. 16th ACM Conference on Economics and Computation (EC), 2015.
• J. Kleinberg, J. Ludwig, S. Mullainathan, Z. Obermeyer. Prediction Policy Problems. American Economic Review: Papers and Proceedings 105:5(2015).
• 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.
• D. Romero, D. Huttenlocher, J. Kleinberg. Coordination and Efficiency in Decentralized Collaboration. Proc. 9th International AAAI Conference on Weblogs and Social Media, 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. 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. 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.

2014

• 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.
• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Engaging with Massive Online Courses. Proc. 23rd International World Wide Web Conference, 2014.
• 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.

  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.

  I. Kloumann, J. Kleinberg. Community membership identification from small seed sets. Proc. 20th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2014.

  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.

2013

• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Steering User Behavior with Badges. Proc. 22nd International World Wide Web Conference, 2013.
• 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.

  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.

  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.

  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.

  A. Ghosh, J. Kleinberg. Incentivizing participation in online forums for education. Proc. 14th ACM Conference on Electronic Commerce, 2013.

  J. Kleinberg, K. Ligett. Information-sharing in social networks. Games and Economic Behavior 82, 2013.

  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. The Pigeonhole Principle. In This Explains Everything. Harper Perennial 2013.

2012

• 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.
• 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.
• 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.
• 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.
• F. Chierichetti, J. Kleinberg, Voting with Limited Information and Many Alternatives. Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, 2012.
• T. Novikoff, J. Kleinberg, S. Strogatz. Education of a Model Student. Proc. National Academy of Sciences, 109(6) 1868-1873, 7 February 2012.
• 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.
• J. Tang, T. Lou, J. Kleinberg. Inferring Social Ties across Heterogenous Networks. Proc. 5th ACM Conference on Web Search and Data Mining, 2012.
• J. Kleinberg. E Pluribus Unum. In This Will Make You Smarter: New Scientific Concepts to Improve Your Thinking. Harper Perennial 2012.

2011

• D. Bindel, J. Kleinberg, S. Oren. How Bad is Forming Your Own Opinion? Proc. 52nd IEEE Symposium on Foundations of Computer Science, 2011.
• 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.
• J. Kleinberg, S. Oren. Mechanisms for (Mis)Allocating Scientific Credit. Proc. 43rd ACM Symposium on Theory of Computing, 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.
• L. Backstrom, J. Kleinberg. Network Bucket Testing. Proc. 20th International World Wide Web Conference, 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. Cheng, D. Romero, B. Meeder, J. Kleinberg. Predicting Reciprocity in Social Networks. Proc. 3rd IEEE Conference on Social Computing, 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.
• 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.
• J. Kleinberg. What Can Huge Datasets Teach Us About Society and Ourselves? In Future Science, Vintage 2011.
• J. Kleinberg. The Human Texture of Information. In Is the Internet Changing the Way You Think? Harper Perennial 2011.

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.
• 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.
• 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.
• 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.
• 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.

2009

• 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.
• 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.

  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.

  S. Marvel, J. Kleinberg, S. Strogatz. The Energy Landscape of Social Balance. Physical Review Letters 103(19), 2009.

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

2008

• 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.

  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.

  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.

  J. Kleinberg. The convergence of social and technological networks. Communications of the ACM, 51(11):66-72, 2008.

  J. Kleinberg, E. Tardos. Balanced Outcomes in Social Exchange Networks. Proc. 40th ACM Symposium on Theory of Computing, 2008.

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

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

  E. Breck, D. Easley, D. Fan, J. Kleinberg, L. Lee, J. Wofford, R. Zabih. A new start: Innovative introductory AI-centered courses at Cornell. Proc. AAAI Spring Symposium, 2008.

  J. Kleinberg. The Mathematics of Algorithm Design. In Princeton Companion to Mathematics, (T. Gowers and J. Barrow-Green, eds.), Princeton Univ. Press, 2008.

2007

• 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.
• L. Blume, D. Easley, J. Kleinberg, E. Tardos. Trading Networks with Price-Setting Agents. Proc. 8th ACM Conference on Electronic Commerce, 2007.
• 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.
• J. Kleinberg The Wireless Epidemic. Nature (News and Views) 449(2007), 287-288.
• 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.
• A. Frieze, J. Kleinberg, R. Ravi, W. Debany. Line-of-Sight Networks. Proc. 18th ACM-SIAM Symposium on Discrete Algorithms, 2007.
• 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.

2006

• 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. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006.
• 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. Leskovec, A. Singh, J. Kleinberg. Patterns of Influence in a Recommendation Network. Proc. Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2006.
• J. Kleinberg. The World at Your Fingertips. Nature (Books and Arts) 440(2006), 279.

2005

• 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.
• J. Kleinberg, P. Raghavan. Query Incentive Networks. Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.
• 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.
• 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.
• 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. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos. Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication. European Conference on Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD), 2005.
• 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.
• R. Kleinberg, J. Kleinberg, Isomorphism and Embedding Problems for Infinite Limits of Scale-Free Graphs. Proc. 15th ACM-SIAM Symposium on Discrete Algorithms, 2005.

2004

• J. Kleinberg, A. Slivkins, T. Wexler. Triangulation and Embedding using Small Sets of Beacons. Proc. 45th IEEE Symposium on Foundations of Computer Science, 2004.
• 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.
• J. Kleinberg, M. Sandler. Using Mixture Models for Collaborative Filtering. Proc. 36th ACM Symposium on Theory of Computing, 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. 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. Kleinberg, M. Sandler, A. Slivkins. Network Failure Detection and Graph Connectivity. Proc. 15th ACM-SIAM Symposium on Discrete Algorithms, 2004. (In PDF.)
• L. Meyerguz, D. Kempe, J. Kleinberg, R. Elber. The Evolutionary Capacity of Protein Structures. Proc. ACM RECOMB Intl. Conference on Computational Molecular Biology, 2004.
• J. Kleinberg, C. Papadimitriou. Computability and Complexity. An essay in Computer Science: Reflections on the Field, Reflections from the Field. National Academies Press, 2004.
• 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. Analysing the scientific literature in its online context. Nature Web Focus on Access to the Literature, April 2004.

2003

• 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.
• D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks. Proc. 12th International Conference on Information and Knowledge Management (CIKM), 2003.
• 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. Gehrke, P. Ginsparg, J. Kleinberg. Overview of the 2003 KDD Cup. SIGKDD Explorations, 2003.
• 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).

2002

• 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.

  J. Kleinberg. An Impossibility Theorem for Clustering. Advances in Neural Information Processing Systems 15, 2002.

  D. Kempe, J. Kleinberg. Protocols and Impossibility Results for Gossip-Based Communication Mechanisms. Proc. 43rd IEEE Symposium on Foundations of Computer Science, 2002.

  E. Anshelevich, D. Kempe, J. Kleinberg. Stability of Load Balancing Algorithms in Dynamic Adversarial Systems. Proc. 34th ACM Symposium on Theory of Computing, 2002.

  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).

  D. Goldberg, S. McCouch, J. Kleinberg. Constructing comparative maps with unresolved marker order. Proc. Pacific Symposium on Biocomputing, 2002.

2001

• J. Kleinberg. Small-World Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems 14, 2001.
• J. Kleinberg, S. Lawrence. The Structure of the Web. Science 294(2001), 1849. This version also appears in the on-line edition of Science.
• D. Kempe, J. Kleinberg, A. Demers. Spatial gossip and resource location protocols. Proc. 33rd ACM Symposium on Theory of Computing, 2001.
• 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, C. Papadimitriou, P. Raghavan. On the Value of Private Information. Proc. 8th Conf. on Theoretical Aspects of Rationality and Knowledge, 2001.
• D. Callaway, J. Hopcroft, J. Kleinberg, M. Newman, S. Strogatz. Are randomly grown graphs really random? Physical Review E 64, 041902 (2001).
• A. Blum, A. Kalai, J. Kleinberg, Admission Control to Minimize Rejections. Proc. 7th International Workshop on Algorithms and Data Structures, 2001.

2000

• 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). (In HTML and PDF.)
• J. Kleinberg. Detecting a Network Failure. Proc. 41st IEEE Symposium on Foundations of Computer Science, 2000.
• A. Kumar, J. Kleinberg. Fairness measures for resource allocation. 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.
• 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.
• 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, C. Papadimitriou, P. Raghavan. Auditing Boolean Attributes. Proc. 19th ACM Symposium on Principles of Database Systems, 2000.

1999

• 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, Y. Rabani, E. Tardos. Fairness in routing and load balancing. Proc. 40th IEEE Symposium on Foundations of Computer Science, 1999.
• 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.
• 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.
• 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.
• 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.
• 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.

1998

• J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Also appears as IBM Research Report RJ 10076, May 1997. (In PDF.)
• D. Gibson, J. Kleinberg, P. Raghavan. Inferring Web communities from link topology. Proc. 9th ACM Conference on Hypertext and Hypermedia, 1998. (In PDF.)
• 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.
• J. Kleinberg, C. Papadimitriou, P. Raghavan. A micro-economic view of data mining. Data Mining and Knowledge Discovery, 2(4), 1998.
• J. Kleinberg, C. Papadimitriou, P. Raghavan. Segmentation problems. Proc. 30th ACM Symposium on Theory of Computing, 1998.
• J. Kleinberg. Decision algorithms for unsplittable flow and the half-disjoint paths problem. Proc. 30th ACM Symposium on Theory of Computing, 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, M. Goemans. The Lovasz theta function and a semi-definite programming relaxation of vertex cover. SIAM J. Discrete Math, 11(1998).

1997

• J. Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. Proc. 29th ACM Symposium on Theory of Computing, 1997.
• J. Kleinberg, Y. Rabani, E. Tardos. Allocating bandwidth for bursty connections. Proc. 29th ACM Symposium on Theory of Computing, 1997.
• J. Kleinberg, R. Motwani, P. Raghavan, S. Venkatasubramanian. Storage management for evolving databases. Proc. 38th IEEE Symposium on Foundations of Computer Science, 1997.

1996

• J. Kleinberg. Single-source unsplittable flow. Proc. 37th IEEE Symposium on Foundations of Computer Science, 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.
• A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, D. Williamson. Adversarial queueing theory. Proc. 28th ACM Symposium on Theory of Computing, 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.
• B. Berger, J. Kleinberg, F.T. Leighton. Reconstructing a Three-Dimensional Model with Arbitrary Errors. Proc. 28th ACM Symposium on Theory of Computing, 1996.
• M. Goemans, J. Kleinberg. An improved approximation ratio for the minimum latency problem. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, 1996.
• J. Kleinberg. Approximation Algorithms for Disjoint Paths Problems. Ph.D Thesis, Dept. of EECS, MIT, 1996.

1995

• 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, 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.
• R. El-Yaniv, J. Kleinberg. Geometric two-server algorithms. Information Processing Letters 53(1995).

1994

• J. Kleinberg. The localization problem for mobile robots. Proc. 35th IEEE Symposium on Foundations of Computer Science, 1994.
• J. Kleinberg. A lower bound for two-server balancing algorithms. Information Processing Letters 51(1994).
• J. Kleinberg. On-line search in a simple polygon. Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, 1994.
• D. Huttenlocher, J. Kleinberg. Comparing point sets under projection. Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, 1994.

1993

• J. Kleinberg, S. Mullainathan. Resource bounds and combinations of consensus objects. Proc. 12th ACM Symposium on Principles of Distributed Computing, 1993.

1992

• 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.