The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
The geometry of graphs and some of its algorithmic applications
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
Pattern Classification and Scene Analysis
Thompson, M., Duda, R. O., & Hart, P. E. (1974) · Leonardo · doi:10.2307/1573081 · Cited by 4,495
Extensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
On the Shannon capacity of a graph
Lovasz, L. (1979) · IEEE Transactions on Information Theory · doi:10.1109/tit.1979.1055985 · Cited by 1,624
Through the Looking-Glass: And What Alice Found There
Carroll, L. (1871) · University of Florida Digital Collections (University of Florida) · Cited by 1,322
van Lint, J. H., & Wilson, R. M. (2001) · Cambridge University Press eBooks · doi:10.1017/cbo9780511987045 · Cited by 1,185
Theory and Applications of Distance Geometry
Blumenthal, L. M. (1970) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,003
The Volume of Convex Bodies and Banach Space Geometry
Pisier, G. (1989) · Cambridge University Press eBooks · doi:10.1017/cbo9780511662454 · Cited by 967
On lipschitz embedding of finite metric spaces in Hilbert space
Bourgain, J. (1985) · Israel Journal of Mathematics · doi:10.1007/bf02776078 · Cited by 560
Leighton, T., & Rao, S. (1988) · [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1988.21958 · Cited by 395
Cited by
Exact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Expander graphs and their applications
Hoory, S., Linial, N., & Wigderson, A. (2006) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-06-01126-8 · Cited by 1,723
Self-citationThe Design of Approximation Algorithms
Williamson, D. P., & Shmoys, D. B. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511921735 · Cited by 1,301
Fixed point and Bregman iterative methods for matrix rank minimization
Ma, S., Goldfarb, D., & Chen, L. (2011) · Mathematical Programming · doi:10.1007/s10107-009-0306-5 · Cited by 1,048
An elementary proof of a theorem of Johnson and Lindenstrauss
Dasgupta, S., & Gupta, A. (2003) · Random Structures & Algorithms · doi:10.1002/rsa.10073 · Cited by 932
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Leighton, T., & Rao, S. (1999) · Journal of the ACM · doi:10.1145/331524.331526 · Cited by 820
Database-friendly random projections
Achlioptas, D. (2001) · Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/375551.375608 · Cited by 699
A Simpler Approach to Matrix Completion
Recht, B. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0910.0651 · Cited by 673
Efficient algorithms for online decision problems
Kalai, A., & Vempala, S. (2005) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2004.10.016 · Cited by 591
The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
Ailon, N., & Chazelle, B. (2009) · SIAM Journal on Computing · doi:10.1137/060673096 · Cited by 479
Index-driven similarity search in metric spaces (Survey Article)
Hjaltason, G. R., & Samet, H. (2003) · ACM Transactions on Database Systems · doi:10.1145/958942.958948 · Cited by 439
An Overview of Low-Rank Matrix Recovery From Incomplete Observations
Davenport, M. A., & Romberg, J. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2016.2539100 · Cited by 439
Three-Dimensional Face Recognition
Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2005) · International Journal of Computer Vision · doi:10.1007/s11263-005-1085-y · Cited by 424
Expander flows, geometric embeddings and graph partitioning
Arora, S., Rao, S., & Vazirani, U. (2009) · Journal of the ACM · doi:10.1145/1502793.1502794 · Cited by 418
Bounded geometries, fractals, and low-distortion embeddings
Gupta, A., Krauthgamer, R., & Lee, J. R. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238226 · Cited by 405
Improved Iteratively Reweighted Least Squares for Unconstrained Smoothed $\ell_q$ Minimization
Lai, M.-J., Xu, Y., & Yin, W. (2013) · SIAM Journal on Numerical Analysis · doi:10.1137/110840364 · Cited by 385
Current progress and open challenges for applying deep learning across the biosciences
Sapoval, N., Aghazadeh, A., Nute, M. G., Antunes, D. A., Balaji, A., Baraniuk, R., Barberan, C. J., Dannenfelser, R., Dun, C., Edrisi, M., et al. (2022) · Nature Communications · doi:10.1038/s41467-022-29268-7 · Cited by 359
Theory of semidefinite programming for Sensor Network Localization
So, A. M.-C., & Ye, Y. (2007) · Mathematical Programming · doi:10.1007/s10107-006-0040-1 · Cited by 326
Randomized numerical linear algebra: Foundations and algorithms
Martinsson, P.-G., & Tropp, J. A. (2020) · Acta Numerica · doi:10.1017/s0962492920000021 · Cited by 300
Expander flows, geometric embeddings and graph partitioning
Arora, S., Rao, S., & Vazirani, U. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007355 · Cited by 297
Virtual landmarks for the internet
Tang, L., & Crovella, M. (2003) · Proceedings of the 2003 ACM SIGCOMM conference on Internet measurement - IMC '03 · doi:10.1145/948205.948223 · Cited by 297
Khot, S. A., & Vishnoi, N. K. (2005) · 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) · doi:10.1109/sfcs.2005.74 · Cited by 263
An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
Aumann, Y., & Rabani, Y. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539794285983 · Cited by 260
Efficient search for approximate nearest neighbor in high dimensional spaces
Kushilevitz, E., Ostrovsky, R., & Rabani, Y. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276877 · Cited by 259
Modularity clustering is force-directed layout
Noack, A. (2009) · Physical Review E · doi:10.1103/physreve.79.026102 · Cited by 258
Metadata
- Authors
- Linial, N., London, E., & Rabinovich, Y.
- Venue
- Combinatorica
- Published
- 1995-06
- Volume
- 15
- Issue
- 2
- Pages
- 215-245
- ISSN
- 0209-9683 (ISSN-L)
- 1439-6912
- OpenAlex
- W2176446742
- Cited by
- 952
- References
- 19
- FWCI
- 14.28
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.