Jon Kleinberg Assistant Professor kleinber@cs.cornell.edu http://www.cs.cornell.edu/home/kleinber/ 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

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. 

Awards 

• ONR Young Investigator Award 
• Alfred P. Sloan Research Fellowship 
• NSF Faculty Early Career Development Award 

• 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
  Hypermedia (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).