Publications

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.

  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. 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? (S. Mullainathan and J. Brockman, editors) 2013.

  J. Kleinberg. The Pigeonhole Principle. In This Explains Everything. (J. Brockman, editor), 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 (J. Brockman, editor), Harper Perennial 2012.

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.
• 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. 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 (NIPS) 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.
  • See also a movie of the process analyzed in this paper, playing out on an artificial social network. Green links indicate friendship, red links indicate antagonism, and black/gray links indicate approximately neutral relations.

  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 (M. Brockman, editor), Vintage 2011.

  J. Kleinberg. The Human Texture of Information. In Is the Internet Changing the Way You Think? (J. Brockman, editor), 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.
  • See also the acommpanying MemeTracker site, which uses the ideas in this paper to visualize the news cycle.

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