1998 - 1999 CS Annual Report                                                                  Faculty
choices.gif (4488 bytes)

Jon Kleinberg

Assistant Professor

PhD MIT, 1996

My research interests are centered around combinatorial algorithms and some of their applications. 

One major focus of my work is in the area of combinatorial optimization, and the development of approximation algorithms for NP-hard problems. With Eva Tardos and
Yuval Rabani, I have been looking at approximation algorithms for routing problems in networks subject to capacity constraints; in recent work we have considered 

settings with an explicit fairness requirement on the allocation of bandwidth. I am also interested in the study of network traffic as a dynamic phenomenon; with Allan Borodin, Prabhakar Raghavan, Madhu Sudan, and David Williamson, we 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. 

Another direction in my work is the use of discrete algorithms for the indexing and clustering of high-dimensional data. I have developed techniques based on spectral graph analysis that use the link structure of hypermedia environments, such as the World Wide Web, for the purpose of identifying "authoritative" information resources. With Christos Papadimitriou and Prabhakar
Raghavan, I have been studying a model of "segmented optimization problems"; this is a
computational framework designed to address some of the optimization issues inherent in certain clustering and data mining operations. With Eva Tardos, I have recently
developed approximation algorithms for a family of classification problems arising from the theory of Markov random fields; we are in the process of exploring further issues in this area together with Yuri Boykov, Olga
Veksler, and Ramin Zabih. 

I am also interested in the development of geometric and combinatorial techniques for algorithmic problems in molecular biology. I am currently involved in work that adapts techniques from discrete optimization to models of protein sequence design proposed in the biophysics 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 protein sequences. At present, I am investigating various models for sequence evolution with Ron Elber. The definition of a robust and efficiently computable notion of "geometric similarity" on three-dimensional protein
conformations is also a problem of considerable interest, and I have been working on the development of such measures with Paul Chew, Dan Huttenlocher and Klara Kedem. 


  • ONR Young Investigator Award 
  • Alfred P. Sloan Research Fellowship 
  • NSF Faculty Early Career Development Award 
University Activities 
  • Chair: Center for Applied Mathematics Colloquium Committee 
  • Computer Science Faculty Recruiting Committee 
  • Statistical Genomics Faculty Recruiting Committee. 
  • Fields of Computer Science, Applied Math, and Operations Research. 
Professional Activities 
  • Program Committee: ACM Symposium on Theory of Computing, 1999; International
    World Wide Web Conference, 1999; International Workshop on Randomization and
    Approximation Techniques in Computer Science, 1999 
  • Algorithms for protein sequence design and evolutionary fitness landscapes. Computer Science, Univ. of Toronto, May 1999.  
  • . Computer Science, Princeton Univ., March 1999. 
  • Analyzing information networks: Hubs, authorities, and communities on the World Wide
    Web. AT&T Labs Research, March 1999. 
  • . NEC Research Institute, March 1999. 
  • . Computer Science, State Univ. of New York at Buffalo, Dec. 1998.
  • . Computer Science, Carnegie Mellon, Nov 1998.  
  • . Computer Science, Univ. Maryland College Park, Sept.. 1998. 
  • Applications of linear algebra in information retrieval and hypertext analysis (tutorial).
    ACM Principles of Database Systems, June 1999. 
  • Nearest-neighbor search in high dimensions. Computer Science, Princeton Univ., March 1999.  
  • Wavelength conversion in optical networks. ACM-SIAM Symposium on Discrete
    Algorithms, Jan. 1999. 
  • 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), 226-237. 
  • Fast detection of common geometric substructure in proteins. Proc. 3rd ACM RECOMB Intl. Conference on Computational Molecular Biology (1999), 104-113 (with L.P. Chew, D. Huttenlocher, K. Kedem).  
  • Hypersearching the web. Scientific American 280 (June 1999), 54-60 (with S. Chakrabarti, B. Dom, D. Gibson, S.R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins). 
  • Wavelength conversion in optical networks. Proc. Tenth ACM-SIAM Symposium on Discrete Algorithms (1999), 566-575 (with A. Kumar).  
  • Minimizing wirelength in zero and bounded skew clock trees. Proc. Tenth ACM-SIAM Symposium on Discrete Algorithms (1999), 177-184 (with M. Charikar, R. Kumar, S. Rajagopalan, A. Sahai, A. Tomkins).  
  • Applications of linear algebra in information retrieval and hypertext analysis. Tutorial survey at the ACM Symposium on Principles of Database Systems (1999) (with A. Tomkins).  
  • A micro-economic view of data mining. Data Mining and Knowledge Discovery 2 (1998), 311-324 (with C.  Papadimitriou and P. Raghavan).  
  • Structural analysis of the WWW. Position paper at the WWW Consortium Web Characterization Workshop, (1998) (with D. Gibson and P. Raghavan.)  
  • Inferring web communities from link topology. Proc. 9th ACM Conference on Hypertext and
    (1998), 225-234 (with D. Gibson and P. Raghavan). 
  • Clustering categorical data: An approach based on dynamical systems. Proc. 24th Intl. Conf. on Very Large Databases (1998), 311-322 (with D. Gibson and P. Raghavan).  
  • Approximations for the disjoint paths problem in high-diameter planar networks. Journal of
    Computer and System Sciences
    57 (1998), 61-73 (with E. Tardos).  
  • An improved approximation ratio for the minimum latency problem. Mathematical Programming B 82 (1998), 111-124 (with M. Goemans).