Jon KleinbergAssistant Professor PhD MIT, 1996My 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 NP-hard 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 packet-routing networks without probabilistic assumptions. | |
I also work on discrete algorithms for indexing and clustering high-dimensional data. I developed methods for performing efficient nearest-neighbor search in high-dimensional Euclidean spaces by "synthesizing" the results of a large number of randomly chosen low-dimensional 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 hyperlink-oriented 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 data-mining 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 three-dimensional conformations is also a problem of considerable interest; I work in this area with P. Chew, D. Huttenlocher, and K. Kedem.
Awards
Alfred P. Sloan Research Fellowship 1997-1999
NSF Faculty Early Career Development Award 1997-2001
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.
___. ACM-SIAM Symp. Discrete Algorithms, Jan. 1998.
___. Computer Science, Univ. Toronto, Nov. 1997.
Analysis of hypermedia. NSF-IMA 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 half-disjoint paths problem. Proc. 30th ACM Symp. Theory Computing (1998), 530-539.
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), 65-74 (with S. Chakrabarti, B. Dom, D. Gibson, P. Raghavan, and S. Rajagopalan).
Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symp. (1998), 668-677.
The Lovasz theta function and a semi-definite programming relaxation of vertex cover. SIAM J. Discrete Math. 11 (1998), 196-204 (with M. Goemans).
Storage management for evolving databases. Proc. 38th IEEE Symp. Found. Computer Science (1997), 353-362 (with R. Motwani, P. Raghavan, and S. Venkatasubramanian).