Now showing items 1-9 of 9

    • Bursty and Hierarchical Structure in Streams 

      Kleinberg, Jon (Cornell University, 2002-03-11)
      A fundamental problem in text data mining is to extract meaningful structure from document streams that arrive continuously over time. E-mail and news articles are two natural examples of such streams, each characterized ...
    • An Efficient Algorithm for Polymer Sequence Design 

      Kleinberg, Jon (Cornell University, 1998-03)
      Polymer sequence design is a natural inverse problem to protein structure prediction: given a target structure in three dimensions, we wish to design an amino acid sequence that will fold to it. A model of Sun, Brem, Chan, ...
    • Efficient Algorithms for Protein Sequence Design and the Analysis ofCertain Evolutionary Fitness Landscapes 

      Kleinberg, Jon (Cornell University, 1998-10)
      Protein sequence design is a natural inverse problem to protein structure prediction: given a target structure in three dimensions, we wish to design an amino acid sequence that is likely fold to it. A model of Sun, Brem, ...
    • Fast Detection of Common Geometric Substructure in Proteins 

      Chew, Paul; Kedem, Klara; Kleinberg, Jon; Huttenlocher, Dan (Cornell University, 1998-09)
      We consider the problem of identifying common three-dimensional substructures between proteins. Our method is based on comparing the shape of the $\alpha$-carbon backbone structures of the proteins in order to find 3D ...
    • A Graph-Based Approach towards Discerning Inherent Structures in a Digital Library of Formal Mathematics 

      Lorigo, Lori; Kleinberg, Jon; Eaton, Richard; Constable, Robert (Cornell University, 2006-01-30)
      As the amount of online formal mathematical content grows, for example through active efforts such as the Mathweb [21], MOWGLI [4], Formal Digital Library, or FDL [1], and others, it becomes increasingly valuable to find ...
    • Metric Embeddings with Relaxed Guarantees 

      Chan, T-H. Hubert; Dhamdhere, Kedar; Gupta, Anupam; Kleinberg, Jon; Slivkins, Aleksandrs Aleksandrs Slivkins (Cornell University, 2006-09-22)
      We consider the problem of embedding finite metrics with "slack": we seek to produce embeddings with small dimension and distortion while allowing a (small) constant fraction of all distances to be arbitrarily distorted. ...
    • Network Failure Detection and Graph Connectivity 

      Kleinberg, Jon; Sandler, Mark; Slivkins, Aleksandrs (Cornell University, 2002-11-22)
      We consider a model for monitoring the connectivity of a network subject to node or edge failures. In particular, we are concerned with detecting \emph{$(\vareps, k)$-failures}: events in which an adversary deletes up ...
    • The Small-World Phenomenon: An Algorithmic Perspective 

      Kleinberg, Jon (Cornell University, 1999-10)
      Long a matter of folklore, the ``small-world phenomenon'' --- the principle that we are all linked by short chains of acquaintances --- was inaugurated as an area of experimental study in the social sciences through the ...
    • Wavelength Conversion in Optical Networks 

      Kleinberg, Jon; Kumar, Amit (Cornell University, 1998-04)
      In many models of optical routing, we are given a set of communication paths in a network, and we must assign a wavelength to each path so that paths sharing an edge receive different wavelengths. The goal is to assign ...