The geometry of graphs and some of its algorithmic applications

By N. Linial, E. London, Yuri Rabinovich. 1994

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Position-aware Graph Neural Networks (2019, methodology): “A constructive proof of Theorem 1 (Linial et al., 1995) provides an algorithm to construct an O (log 2 n ) dimensional embedding via anchor-sets, as summarized in Theorem 2: Theorem 2.”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, background): “Observe that the `1 distance between any two points is equal to the Hamming distance of their images [44].”
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy (2012, background): “A very non-exhaustive list of related applications include metric and graph embed-dings [Bou85, LLR94], computational speedups [Sar06, Vem05], machine learning [BBV06, Sch00], information retrieval [PRT + 98], nearest-neighbor search [Kle97, IM98, AC06], and compressed sensing [BDDW08].”
The Fast Johnson--Lindenstrauss Transform and Approximate Nearest Neighbors (2009, background): “Linial, London, and Rabinovich in their seminal paper [34] first considered the algorithmic applications of metric embeddings.”
The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/ (2005, background): “We show that for an arbitrarily small constant δ > 0, for all large enough n, there is an n-point negative type metric which requires distortion at least (log log n)1/6−δ to embed into 1.”
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions (2006, background): “Moreover, a simple reduction enables the extension of this family of functions to M-ary vectors under the l1 distance [30].”
Estimating 3D hand pose from a cluttered image (2003, methodology): “A class of embeddings often used in this context are Lipschitz embeddings [4, 13].”
Optimal hierarchical decompositions for congestion minimization in networks (2008, background): “Again this is not new (see [24, 7, 25]) but it seems interesting that this ratio can be obtained while only looking at a restricted number of cuts.”
Finding Motifs Using Random Projections (2001, unknown): “…of points in a high-dimensionalmetric space appears in Indyk and Motwani’s work on “locality-sensitive hashing” (Indyk and Motwani, 1998; Gionis et al. , 1999), building on theoretical work in random projection by, e.g., Johnson and Lindenstrauss (1984), Bourgain (1985), and Linial et al. (1994).”
Geographic Routing Using Hyperbolic Space (2007, background): “3 of Linial, London and Rabinovich’s classic paper [20].”