Now showing items 4-9 of 9

    • 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 ...