Jon Kleinberg
Assistant Professor
kleinber@cs.cornell.edu
http://www.cs.cornell.edu/home/kleinber/
PhD MIT, 1996
My research interests are centered around discrete algorithms and
some of their applications.
One major focus of my work is in combinatorial optimization and
approximation algorithms for NPhard problems. E. Tardos, Y. Rabani, and I have been
looking at approximation algorithms for routing problems in networks subject to capacity
constraints; some of our recent work has considered cases in which the bandwidth
requirements of connections are bursty, and modeled in a probabilistic framework. I am
also interested in the study of network traffic as a dynamic phenomenon; A. Borodin, P.
Raghavan, 

M. Sudan, D. Williamson and I developed
and analyzed an "adversarial" model for the evolution of traffic in a network,
which allows one to study the stability properties of packetrouting networks without
probabilistic assumptions. 
I also work on discrete algorithms for indexing and
clustering highdimensional data. I developed methods for performing efficient
nearestneighbor search in highdimensional Euclidean spaces by "synthesizing"
the results of a large number of randomly chosen lowdimensional projections. I have
developed techniques—based on spectral graph analysis—to use the link structure
of a hypermedia environment such as the World Wide Web in order to identify
"authoritative" information resources. The continued development of these
techniques into a general methodology for hyperlinkoriented search tasks is being pursued
with S. Chakrabarti, B. Dom, D. Gibson, P. Raghavan, and S. Rajagopalan. And, with C.
Papadimitriou and P. Raghavan, I have been studying a model of "segmented
optimization problems", which are designed to address some of the optimization issues
inherent in certain clustering and datamining operations.
I am also interested in geometric and combinatorial
techniques for algorithmic problems in molecular biology. I am adapting techniques from
discrete optimization to models of polymer sequence design proposed in the biochemistry
community. In addition to providing efficient algorithms, these techniques offer a novel
computational perspective from which to study the structure of certain "evolutionary
networks" on polymer sequences. The definition of a robust and efficiently computable
notion of "geometric similarity" on threedimensional conformations is also a
problem of considerable interest; I work in this area with P. Chew, D. Huttenlocher, and
K. Kedem.
Awards
University Activities
Computer Science Faculty Recruiting Committee,
Fields of Computer Science, Applied Math, and Operations Research
Professional Activities
Program Committee: IEEE Symp. Foundations of
Computer Science, 1998; Int. Workshop on the Web and Databases, 1998
Lectures
Authoritative sources in a hyperlinked
environment. Computer Science, MIT, April 1998.
___. Computer Science, Brown Univ., April 1998.
___. ACMSIAM Symp. Discrete Algorithms, Jan.
1998.
___. Computer Science, Univ. Toronto, Nov. 1997.
Analysis of hypermedia. NSFIMA Workshop on
Knowledge and Distributed Intelligence, March 1998.
Decision algorithms for unsplittable flow. ACM.
Theory of Computing, May 1998.
Publications
Decision algorithms for unsplittable flow and the
halfdisjoint paths problem. Proc. 30th ACM Symp. Theory Computing (1998), 530539.
Segmentation problems. Proc. 30th ACM Symp.
Theory of Computing(1998). (with C. Papadimitriou and P. Raghavan).
Automatic resource compilation by analyzing
hyperlink structure and associated text. Proc. 7th Int. World Wide Web Conf.
(1998), 6574 (with S. Chakrabarti, B. Dom, D. Gibson, P. Raghavan, and S. Rajagopalan).
Authoritative sources in a hyperlinked
environment. Proc. 9th ACMSIAM Symp. (1998), 668677.
The Lovasz theta function and a semidefinite
programming relaxation of vertex cover. SIAM J. Discrete Math. 11 (1998), 196204
(with M. Goemans).
Storage management for evolving databases. Proc.
38th IEEE Symp. Found. Computer Science (1997), 353362 (with R. Motwani, P. Raghavan,
and S. Venkatasubramanian).
