Publications

Papers are listed by the year of the conference version.

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.

  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, to appear.

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.
• J. Kleinberg, C. Papadimitriou, P. Raghavan. Segmentation problems. Journal of the ACM, 51(2), 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.
• 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.)
• D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks. Proc. 12th International Conference on Information and Knowledge Management (CIKM), 2003.
• 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

• D. Kempe, J. Kleinberg, A. Demers. Spatial gossip and resource location protocols. Proc. 33rd ACM Symposium on Theory of Computing, 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.
• 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.
• 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. Decision algorithms for unsplittable flow and the half-disjoint paths problem. Proc. 30th ACM Symposium on Theory of Computing, 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.