Jon Kleinberg
 Tisch University Professor
 Department of Computer Science
 Department of Information Science
 Cornell University
 Ithaca, NY 14853
I am a professor at Cornell University.
My research focuses on
issues at the interface of networks and information, with
an emphasis on the social and information networks that underpin the
Web and other online media.
My work has been supported by an
NSF Career Award,
an ONR Young Investigator Award,
a
MacArthur Foundation Fellowship,
a
Packard Foundation Fellowship,
a
Simons Investigator Award,
a
Sloan Foundation Fellowship,
and grants from Facebook, Google, Yahoo!, the ARO, and the NSF.
I am a member of
the
National Academy of Sciences,
the
National Academy of Engineering,
and the
American Academy of Arts and Sciences.
Link to: Contact information.

D. Easley, J. Kleinberg.
Networks, Crowds, and Markets: Reasoning About a Highly Connected World.
Cambridge University Press, 2010.

This book is based on an interdisciplinary course that we teach entitled
Networks.
The book, like the
course, is designed at the introductory undergraduate
level with no formal prerequisites. To support deeper
explorations, most of the chapters are supplemented with
optional advanced sections.

J. Kleinberg, E. Tardos.
Algorithm Design.
Addison Wesley, 2005.

This book is based on the undergraduate algorithms course that we both teach.
We also use the more advanced parts for our graduate algorithms course.

An online course on edX entitled
Networks, Crowds, and Markets,
with David Easley and Eva Tardos.

Recent courses at Cornell:
Advising
 Current and former Ph.D. students:
Isabel Kloumann,
Maithra Raghu,
Rahmtin Rotabi,
Rediet Abebe,
Johan Ugander (Stanford),
Sigal Oren (BenGurion Univ),
Daniel Romero (U. Michigan),
Lars Backstrom (Facebook),
Alex Slivkins (Microsoft Research),
Mark Sandler (Google),
Elliot Anshelevich (RPI),
David Kempe (USC),
Amit Kumar. (IIT Dehli),
Debra Goldberg (CU Boulder).
 Current and former postdocs:
Flavio Chierichetti (Sapienza University of Rome),
Jure Leskovec (Stanford),
Sid Suri (Microsoft Research),
Gueorgi Kossinets. (Google),
Mohammad Mahdian (Google),
Frank McSherry (Microsoft Research)
Anupam Gupta (CMU).
Recent Papers

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.

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.

M. Luca, J. Kleinberg, S. Mullainathan.
Algorithms Need Managers, Too.
Harvard Business Review, 94:1(Jan/Feb 2016).
Web Analysis and Search: Hubs and Authorities
 J. Kleinberg. Authoritative sources
in a hyperlinked environment.
Proc. 9th ACMSIAM Symposium on Discrete Algorithms, 1998.
Extended version in Journal of the ACM 46(1999).
Also appears as IBM Research Report RJ 10076, May 1997.
 D. Gibson, J. Kleinberg, P. Raghavan.
Inferring Web communities from link topology.
Proc. 9th ACM Conference on Hypertext and Hypermedia, 1998.
 S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg,
P. Raghavan, S. Rajagopalan,
Automatic resource list compilation by
analyzing hyperlink structure and associated text.
Proc. 7th International World Wide Web Conference, 1998.
 S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar,
P. Raghavan, S. Rajagopalan, A. Tomkins,
Hypersearching the Web.
Scientific American, June 1999.
 S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar,
P. Raghavan, S. Rajagopalan, A. Tomkins,
Mining the link structure of the World Wide Web.
IEEE Computer, August 1999.
SmallWorld Phenomena and Decentralized Search
Information Flow and Cascading Behavior in Networks

A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec.
Global Diffusion via Cascading Invitations: Structure, Growth, and Homophily.
Proc. 24th International World Wide Web Conference, 2015.

I. Kloumann, L. Adamic, J. Kleinberg, S. Wu.
The Lifecycles of Apps in a Social Ecosystem.
Proc. 24th International World Wide Web Conference, 2015.

J. Cheng, L. Adamic, A. Dow, J. Kleinberg, J. Leskovec.
Can Cascades Be Predicted?
Proc. 23rd International World Wide Web Conference, 2014.


L. Backstrom, J. Kleinberg, L. Lee, C. DanescuNiculescuMizil.
Characterizing and Curating Conversation Threads: Expansion, Focus,
Volume, Reentry.
Proc. 6th ACM Conference on Web Search and Data Mining, 2013.

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

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

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

K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, A. Sharma.
Preventing Unraveling in Social Networks:
The Anchored kCore Problem,
Proc. 39th International Colloquium on
Automata, Languages and Programming (ICALP), 2012.
 F. Chierichetti, J. Kleinberg, A. Panconesi.
How to schedule a cascade in an arbitrary graph.
Proc. 13th ACM Conference on Electronic Commerce, 2012.

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

L. Blume, D. Easley, J. Kleinberg, R. Kleinberg, E. Tardos.
Network Formation in the Presence of Contagious Risk.
Proc. 12th ACM Conference on Electronic Commerce, 2011.
 F. Chierichetti, J. Kleinberg, D. LibenNowell.
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.

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

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

D. LibenNowell, J. Kleinberg.
Tracing
Information Flow on a Global Scale Using Internet ChainLetter
Data. Proc. National Academy of Sciences,
105(12):4633–4638, 25 March 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.

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

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

J. Kleinberg
The Wireless Epidemic.
Nature (News and Views) 449(2007), 287288.

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

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

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

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

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

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

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

J. Kleinberg, S. Mullainathan.
We Built Them, But We Don't Understand Them.
In The Edge Annual Question: What Do You Think About Machines That Think? (J. Brockman, editor), 2015.
Incentives and GameTheoretic Analysis

J. Kleinberg, S. Oren.
Dynamic Models of Reputation and Competition in JobMarket Matching.
Proc. 6th Conference on Innovations in Theoretical Computer Science (ITCS),
2015.

L. Blume, D. Easley, J. Kleinberg, R. Kleinberg, E. Tardos.
Introduction to computer science and economic theory.
Journal of Economic Theory 156(2015).

J. Kleinberg, S. Oren.
TimeInconsistent Planning: A Computational Problem in Behavioral Economics.
Proc. 15th ACM Conference on Economics and Computation (EC), 2014.

P. Frazier, D. Kempe, J. Kleinberg, R. Kleinberg.
Incentivizing Exploration.
Proc. 15th ACM Conference on Economics and Computation (EC), 2014.

A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec.
Steering User Behavior with Badges.
Proc. 22nd International World Wide Web Conference, 2013.
 F. Chierichetti, J. Kleinberg.
Voting with Limited Information and Many Alternatives.
Proc. 23rd ACMSIAM Symposium on Discrete Algorithms, 2012.

J. Kleinberg, S. Oren.
Mechanisms for (Mis)Allocating Scientific Credit.
Proc. 43rd ACM Symposium on Theory of Computing, 2011.

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

L. Blume, D. Easley, J. Kleinberg, E. Tardos.
Trading Networks with PriceSetting Agents.
Proc. 8th ACM Conference on Electronic Commerce, 2007.

J. Kleinberg, P. Raghavan.
Query Incentive Networks.
Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.
 E. Anshelevich, A. Dasgupta,
J. Kleinberg, E. Tardos, T. Wexler, T. Roughgarden.
The Price of Stability for Network Design with
Fair Cost Allocation.
Proc. 45th IEEE Symposium on Foundations of Computer Science, 2004.
Team Formation and Dynamics
Network Formation and Network Evolution

L. Backstrom, J. Kleinberg.
Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook.
Proc. 17th ACM Conference on Computer Supported Cooperative Work and Social Computing (CSCW), 2014.

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

J. Ugander, L. Backstrom, J. Kleinberg.
Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections.
Proc. 22nd International World Wide Web Conference, 2013.

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

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

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

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

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

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

J. Kleinberg, S. Suri, E. Tardos, T. Wexler.
Strategic Network Formation with Structural Holes.
Proc. 9th ACM Conference on Electronic Commerce, 2008.
 J. Leskovec, J. Kleinberg, C. Faloutsos.
Graphs over Time: Densification Laws, Shrinking Diameters and
Possible Explanations.
Proc. 11th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining,
2005.
 R. Kleinberg, J. Kleinberg,
Isomorphism and Embedding Problems for Infinite Limits of ScaleFree Graphs.
Proc. 16th ACMSIAM Symposium on Discrete Algorithms, 2005.

D. LibenNowell, J. Kleinberg.
The Link Prediction Problem for Social Networks.
Proc. 12th International Conference on Information
and Knowledge Management (CIKM), 2003.
 D. Callaway, J. Hopcroft, J. Kleinberg, M. Newman, S. Strogatz.
Are randomly grown graphs really random?
Physical Review E 64, 041902 (2001).
Opinion, Evaluation, and Polarization
 A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec.
Effects of User Similarity in Social Media.
Proc. 5th ACM Conference on Web Search and Data Mining, 2012.

A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec.
Discovering Value from Community Activity on Focused Question Answering Sites: A Case Study of Stack Overflow.
Proc. 18th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2012.

D. Bindel, J. Kleinberg, S. Oren.
How Bad is Forming Your Own Opinion?
Proc. 52nd IEEE Symposium on Foundations of Computer Science, 2011.

S. Marvel, J. Kleinberg, R. Kleinberg, S. Strogatz.
ContinuousTime Model of Structural Balance.
Proc. National Academy of Sciences, 108(5) 17711776, 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. Leskovec, D. Huttenlocher, J. Kleinberg.
Governance in Social Media:
A case study of the Wikipedia promotion process.
Proc. 4th International AAAI Conference on Weblogs and Social Media, 2010.

J. Leskovec, D. Huttenlocher, J. Kleinberg.
Signed Networks in Social Media.
Proc. 28th ACM SIGCHI Conference on Human Factors in Computing Systems (CHI), 2010.

J. Leskovec, D. Huttenlocher, J. Kleinberg.
Predicting Positive and Negative Links in Online Social Networks.
Proc. 19th International World Wide Web Conference, 2010.

S. Marvel, J. Kleinberg, S. Strogatz.
The Energy Landscape of
Social Balance.
Physical Review Letters 103(19), 2009.
 C. DanescuNiculescuMizil, G. Kossinets, J. Kleinberg, L. Lee.
How Opinions are Received by Online Communities:
A Case Study on Amazon.com Helpfulness Votes.
Proc. 18th International World Wide Web Conference, 2009.
Temporal Analysis and Bursty Phenomena

F. Chierichetti, J. Kleinberg, R. Kumar, M. Mahdian, S. Pandey.
Event Detection via Communication Pattern Analysis.
Proc. 8th International AAAI Conference on Weblogs and Social Media, 2014.

J. Leskovec, L. Backstrom, J. Kleinberg.
Memetracking 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.
 J. Kleinberg.
Temporal Dynamics of
OnLine Information Streams.
In Data Stream Management: Processing HighSpeed Data Streams,
(M. Garofalakis, J. Gehrke, R. Rastogi, eds.), Springer, 2004.
 J. Aizen, D. Huttenlocher, J. Kleinberg, A. Novak.
TrafficBased Feedback on the Web.
Proceedings of the National Academy of Sciences 101(Suppl.1):52545260, 2004.
(Also available in preprint form.)
 J. Kleinberg.
Bursty and Hierarchical Structure in Streams.
Proc. 8th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2002.
 See also some sample results
from the burst detection algorithm described in this paper.
Language, Text Content, and Social Interaction
Algorithms and Models for OnLine Education

A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec.
Engaging with Massive Online Courses.
Proc. 23rd International World Wide Web Conference, 2014.

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

T. Novikoff, J. Kleinberg, S. Strogatz.
Education of a Model Student.
Proc. National Academy of Sciences, 109(6) 18681873, 7 February 2012.
Privacy in Network Analysis and Data Mining

D. Crandall, L. Backstrom, D. Cosley, S. Suri, D. Huttenlocher, J. Kleinberg.
Inferring Social Ties from Geographic Coincidences.
Proc. National Academy of Sciences 107(52) 2243622441, 28 December 2010.

L. Backstrom, C. Dwork, J. Kleinberg.
Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and Structural Steganography.
Proc. 16th Intl. World Wide Web Conference, 2007.
 J. Kleinberg, C. Papadimitriou, P. Raghavan.
Auditing Boolean Attributes.
Proc. 19th ACM Symposium on Principles of Database Systems, 2000.
Spatial Embeddings of Information
Gossip Algorithms in Networks
General Articles on Web Information and OnLine Social Networks

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.
E Pluribus Unum.
In
This Will Make You Smarter: New Scientific Concepts to Improve Your Thinking
(J. Brockman, editor), Harper Perennial 2012.

J. Kleinberg.
The Human Texture of Information.
In
Is the Internet Changing the Way You Think?
(J. Brockman, editor), Harper Perennial 2011.

J. Kleinberg.
What Can Huge Datasets Teach Us About Society and Ourselves?
In Future Science (M. Brockman, editor), Vintage 2011.

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

J. Kleinberg, S. Lawrence.
The Structure of the Web. Science 294(2001), 1849.
This version also appears in the
online edition of Science.
 J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins.
The Web as a graph: Measurements, models and methods.
Invited survey at the International Conference
on Combinatorics and Computing, 1999.
General Articles on Algorithms, Complexity, and Discrete Math
Clustering, Indexing, and Data Mining

A. Dasgupta, J. Hopcroft, J. Kleinberg, M. Sandler.
On Learning Mixtures
of HeavyTailed Distributions.
Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.
 J. Kleinberg, M. Sandler.
Using Mixture Models for Collaborative Filtering.
Proc. 36th ACM Symposium on Theory of Computing, 2004.
 J. Kleinberg, C. Papadimitriou, P. Raghavan.
Segmentation problems.
Journal of the ACM, 51(2), 2004.

P. Felzenszwalb, D. Huttenlocher, J. Kleinberg.
Fast Algorithms for LargeStateSpace 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. Kleinberg.
An Impossibility Theorem for Clustering.
Advances in Neural Information Processing Systems (NIPS) 15, 2002.
 J. Kleinberg, C. Papadimitriou, P. Raghavan.
On the Value of Private Information.
Proc. 8th Conf. on Theoretical Aspects of Rationality and Knowledge, 2001.
 J. Kleinberg, E. Tardos.
Approximation Algorithms for
Classification Problems with Pairwise Relationships:
Metric Labeling and Markov Random Fields.
Proc. 40th IEEE Symposium on Foundations of Computer Science, 1999.
 J. Kleinberg, C. Papadimitriou, P. Raghavan.
A microeconomic
view of data mining.
Data Mining and Knowledge Discovery, 2(4), 1998.
 D. Gibson, J. Kleinberg, P. Raghavan.
Clustering categorical data: An approach based on
dynamical systems.
Proc. 24th Intl. Conference on Very Large Databases, 1998.
 J. Kleinberg. Two algorithms
for nearestneighbor search in high dimensions.
Proc. 29th ACM Symposium on Theory of Computing, 1997.
Network Analysis, Management, and Routing

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.

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

A. Frieze, J. Kleinberg, R. Ravi, W. Debany.
LineofSight Networks.
Proc. 18th ACMSIAM Symposium on Discrete Algorithms, 2007.

A. Krause, C. Guestrin, A. Gupta, J. Kleinberg.
Nearoptimal Sensor Placements: Maximizing Information
while Minimizing Communication Cost.
Proc. Information Processing in Sensor Networks (IPSN), 2006.

J. Kleinberg.
An Approximation Algorithm for the
Disjoint Paths Problem in EvenDegree Planar Graphs.
Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.

I. Abraham, Y. Bartal, TH. Chan, K. Dhamdhere,
A. Gupta, J. Kleinberg, O. Neiman, A. Slivkins.
Metric Embeddings with Relaxed Guarantees.
Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.
 J. Kleinberg, A. Slivkins, T. Wexler.
Triangulation and Embedding
using Small Sets of Beacons.
Proc. 45th IEEE Symposium on Foundations of Computer Science, 2004.
 J. Kleinberg, M. Sandler, A. Slivkins.
Network Failure Detection and
Graph Connectivity.
Proc. 15th ACMSIAM Symposium on Discrete Algorithms, 2004.
(In PDF.)
 A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, B. Yener.
Provisioning a virtual private network:
A network design problem for multicommodity flow.
Proc. 33rd ACM Symposium on Theory of Computing, 2001.
 J. Kleinberg.
Detecting a Network Failure.
Proc. 41st IEEE Symposium on Foundations of Computer Science, 2000.
 D. Kempe, J. Kleinberg, A. Kumar.
Connectivity and inference problems for temporal networks.
Proc. 32nd ACM Symposium on Theory of Computing, 2000.
 R. Fagin, A. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan,
R. Rubinfeld, M. Sudan, A. Tomkins.
Random Walks with `Back Buttons.'
Proc. 32nd ACM Symposium on Theory of Computing, 2000.
 J. Kleinberg, A. Kumar. Wavelength
conversion in optical networks.
Proc. 10th ACMSIAM 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 ACMSIAM Symposium on Discrete Algorithms, 1999.
 J. Kleinberg. Decision algorithms for
unsplittable flow and the halfdisjoint paths problem.
Proc. 30th ACM Symposium on Theory of Computing, 1998.
 J. Kleinberg, Y. Rabani, E. Tardos.
Allocating bandwidth for bursty connections.
Proc. 29th ACM Symposium on Theory of Computing, 1997.
 J. Kleinberg. Singlesource unsplittable flow.
Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996.
 J. Kleinberg, R. Rubinfeld. Short paths
in expander graphs.
Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996.
 A. Aggarwal, J. Kleinberg, D. Williamson.
Nodedisjoint
paths on the mesh, and a new tradeoff in VLSI layout.
Proc. 28th ACM Symposium on Theory of Computing, 1996.
 J. Kleinberg, E. Tardos. Disjoint
paths in densely embedded graphs.
Proc. 36th IEEE Symposium on Foundations of Computer Science,
1995.
 J. Kleinberg, E. Tardos. Approximations
for the disjoint paths problem in highdiameter planar networks.
Proc. 27th ACM Symposium on Theory of Computing, 1995.
 J. Kleinberg. Approximation Algorithms
for Disjoint Paths Problems.
Ph.D Thesis, Dept. of EECS, MIT, 1996.
Dynamic Network Algorithms and Adversarial Queueing Theory
 A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, D. Williamson.
Adversarial queueing theory.
Proc. 28th ACM Symposium on Theory of Computing, 1996.
 D.M. Andrews, B. Awerbuch, A. Fernandez,
J. Kleinberg, F.T. Leighton, Z. Liu.
Universal stability results for greedy
contentionresolution protocols.
Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996.
 E. Anshelevich, D. Kempe, J. Kleinberg.
Stability of Load Balancing Algorithms in Dynamic Adversarial Systems.
Proc. 34th ACM Symposium on Theory of Computing, 2002.
Fairness in Optimization
Comparative Genomics and Evolutionary Models
 L. Meyerguz, J. Kleinberg, R. Elber.
The
network of sequence flow between protein structures.
Proceedings of the National Academy of Sciences 10.1073, 27 June 2007.
 L. Meyerguz, D. Kempe, J. Kleinberg, R. Elber.
The Evolutionary Capacity
of Protein Structures.
Proc. ACM RECOMB Intl. Conference on Computational Molecular Biology, 2004.
 I. V. Yap, D. Schneider, J. Kleinberg, D. Matthews, S. Cartinhour,
S. R. McCouch.
A GraphTheoretic Approach to Comparing and Integrating Genetic,
Physical and SequenceBased Maps.
Genetics, Vol. 165(2003).
 D. Goldberg, S. McCouch, J. Kleinberg.
Constructing comparative maps with unresolved marker
order.
Proc. Pacific Symposium on Biocomputing, 2002.
 D. Goldberg, S. McCouch, J. Kleinberg.
Algorithms for Constructing Comparative Maps.
Conference on Gene Order Dynamics, Comparative Maps, and Multigene Families,
2000.
(In PDF.)
 J. Kleinberg, D. LibenNowell.
The Syntenic Diameter of the Space of
NChromosome Genomes.
Conference on Gene Order Dynamics, Comparative Maps, and Multigene Families,
2000.
 J. Kleinberg.
Efficient Algorithms for Protein Sequence Design
and the Analysis of Certain
Evolutionary Fitness Landscapes.
Proc. 3rd ACM RECOMB Intl. Conference on Computational
Molecular Biology, 1999.
Protein Structure Analysis
OnLine Algorithms
 M. Charikar, R. Fagin, V. Guruswami, J. Kleinberg, P. Raghavan, A. Sahai.
Query
strategies for priced information.
Proc. 32nd ACM Symposium on Theory of Computing, 2000.
 J. Kleinberg, R. Motwani, P. Raghavan, S. Venkatasubramanian.
Storage management for evolving databases.
Proc. 38th IEEE Symposium on Foundations of Computer Science, 1997.
 J. Kleinberg. The localization problem for
mobile robots. Proc. 35th IEEE Symposium on Foundations of Computer
Science, 1994.
 J. Kleinberg. Online search in a simple
polygon. Proc. 5th ACMSIAM Symposium on Discrete Algorithms, 1994.
 J. Kleinberg. A lower bound for twoserver
balancing algorithms. Information Processing Letters 51(1994).
 R. ElYaniv, J. Kleinberg. Geometric twoserver
algorithms. Information Processing Letters 53(1995).
Algorithms for NPhard problems
 E. Dantsin, A. Goerdt, E. Hirsch,
R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schoning,
A deterministic algorithm for satisfiability
based on local search. Theoretical Computer Science, 289(2002).
 J. Kleinberg, M. Goemans. The Lovasz theta
function and a semidefinite programming relaxation of vertex cover.
SIAM J. Discrete Math, 11(1998).
 M. Goemans, J. Kleinberg. An improved
approximation ratio for the minimum latency problem.
Proc. 7th ACMSIAM Symposium on Discrete Algorithms, 1996.
Faulttolerance in Distributed Computing
Geometric Pattern Matching
Jon Kleinberg
Computing and Information Science
Gates Hall
Cornell University
Ithaca, NY 14853
(607)2559197