{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T02:31:03Z","timestamp":1775097063758,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T00:00:00Z","timestamp":1720656000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T00:00:00Z","timestamp":1720656000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2024,12]]},"abstract":"Abstract<\/jats:title>Let G<\/jats:italic> be a 3-connected ordered graph with n<\/jats:italic> vertices and m<\/jats:italic> edges. Let $$\\textbf{p}$$<\/jats:tex-math>\n p<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be a randomly chosen mapping of these n<\/jats:italic> vertices to the integer range $$\\{1, 2,3, \\ldots , 2^b\\}$$<\/jats:tex-math>\n \n {<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n 2<\/mml:mn>\n ,<\/mml:mo>\n 3<\/mml:mn>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n 2<\/mml:mn>\n b<\/mml:mi>\n <\/mml:msup>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for $$b\\ge m^2$$<\/jats:tex-math>\n \n b<\/mml:mi>\n \u2265<\/mml:mo>\n \n m<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Let $$\\ell $$<\/jats:tex-math>\n \u2113<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be the vector of m<\/jats:italic> Euclidean lengths of G<\/jats:italic>\u2019s edges under $$\\textbf{p}$$<\/jats:tex-math>\n p<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In this paper, we show that, with high probability over $$\\textbf{p}$$<\/jats:tex-math>\n p<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we can efficiently reconstruct both G<\/jats:italic> and $$\\textbf{p}$$<\/jats:tex-math>\n p<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> from $$\\ell $$<\/jats:tex-math>\n \u2113<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This reconstruction problem is NP-HARD in the worst case, even if both G<\/jats:italic> and $$\\ell $$<\/jats:tex-math>\n \u2113<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are given. We also show that our results stand in the presence of small amounts of error in $$\\ell $$<\/jats:tex-math>\n \u2113<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and in the real setting, with sufficiently accurate length measurements. Our method combines lattice reduction, which has previously been used to solve random subset sum problems, with an algorithm of Seymour that can efficiently reconstruct an ordered graph given an independence oracle for its matroid.<\/jats:p>","DOI":"10.1007\/s00493-024-00119-x","type":"journal-article","created":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T13:01:56Z","timestamp":1720702916000},"page":"1325-1351","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Reconstruction in One Dimension from Unlabeled Euclidean Lengths"],"prefix":"10.1007","volume":"44","author":[{"given":"Robert","family":"Connelly","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steven J.","family":"Gortler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louis","family":"Theran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,11]]},"reference":[{"key":"119_CR1","unstructured":"Andoni, A., Hsu, D., Shi, K., Sun, X.: Correspondence retrieval. In: Conference on Learning Theory, pp. 105\u2013126. PMLR (2017)"},{"key":"119_CR2","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s10479-018-2989-6","volume":"271","author":"SJ Billinge","year":"2018","unstructured":"Billinge, S.J., Duxbury, P.M., Gon\u00e7alves, D.S., Lavor, C., Mucherino, A.: Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures. Ann. Oper. Res. 271, 161\u2013203 (2018)","journal-title":"Ann. Oper. Res."},{"issue":"3","key":"119_CR3","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1287\/moor.5.3.321","volume":"5","author":"RE Bixby","year":"1980","unstructured":"Bixby, R.E., Cunningham, W.H.: Converting linear programs to network problems. Math. Oper. Res. 5(3), 321\u2013357 (1980). https:\/\/doi.org\/10.1287\/moor.5.3.321","journal-title":"Math. Oper. Res."},{"issue":"4","key":"119_CR4","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1016\/S0196-8858(03)00101-5","volume":"32","author":"M Boutin","year":"2004","unstructured":"Boutin, M., Kemper, G.: On reconstructing $$n$$-point configurations from the distribution of distances or areas. Adv. Appl. Math. 32(4), 709\u2013735 (2004). https:\/\/doi.org\/10.1016\/S0196-8858(03)00101-5","journal-title":"Adv. Appl. Math."},{"key":"119_CR5","doi-asserted-by":"crossref","unstructured":"Cieliebak, M., Eidenbenz, S., Penna, P..: Noisy data make the partial digest problem np-hard. In: International Workshop on Algorithms in Bioinformatics, pp. 111\u2013123. Springer (2003)","DOI":"10.1007\/978-3-540-39763-2_9"},{"key":"119_CR6","doi-asserted-by":"publisher","unstructured":"Connelly, R.: On generic global rigidity. In: Applied geometry and discrete mathematics, volume\u00a04 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci. Amer. Math. Soc., Providence, RI. pp. 147\u2013155. (1991) https:\/\/doi.org\/10.1090\/dimacs\/004\/11","DOI":"10.1090\/dimacs\/004\/11"},{"issue":"4","key":"119_CR7","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/s00454-004-1124-4","volume":"33","author":"R Connelly","year":"2005","unstructured":"Connelly, R.: Generic global rigidity. Discrete Comput. Geom. 33(4), 549\u2013563 (2005). https:\/\/doi.org\/10.1007\/s00454-004-1124-4","journal-title":"Discrete Comput. Geom."},{"key":"119_CR8","volume-title":"Distance Geometry and Molecular Conformation, Volume\u00a015 of Chemometrics Series","author":"GM Crippen","year":"1988","unstructured":"Crippen, G.M., Havel, T.F.: Distance Geometry and Molecular Conformation, Volume\u00a015 of Chemometrics Series. Research Studies Press, Ltd., Chichester (1988)"},{"key":"119_CR9","unstructured":"Dattorro, J.: Convex optimization and Euclidean distance geometry. Online book. (2015). https:\/\/ccrma.stanford.edu\/~dattorro\/0976401304_v2015.04.11.pdf"},{"key":"119_CR10","unstructured":"Diakonikolas, I., Kane, D.: Non-gaussian component analysis via lattice basis reduction. In: Conference on Learning Theory, PMLR. pp. 4535\u20134547 (2022)"},{"key":"119_CR11","volume-title":"Graph Theory, Volume 173 of Graduate Texts in Mathematics","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory, Volume 173 of Graduate Texts in Mathematics. Springer, Berlin (2017)"},{"key":"119_CR12","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.dam.2015.10.029","volume":"204","author":"PM Duxbury","year":"2016","unstructured":"Duxbury, P.M., Granlund, L., Gujarathi, S., Juhas, P., Billinge, S.J.: The unassigned distance geometry problem. Discret. Appl. Math. 204, 117\u2013132 (2016)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"119_CR13","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1137\/0215038","volume":"15","author":"AM Frieze","year":"1986","unstructured":"Frieze, A.M.: On the Lagarias\u2013Odlyzko algorithm for the subset sum problem. SIAM J. Comput. 15(2), 536\u2013539 (1986). https:\/\/doi.org\/10.1137\/0215038","journal-title":"SIAM J. Comput."},{"issue":"12","key":"119_CR14","doi-asserted-by":"publisher","first-page":"8109","DOI":"10.1109\/TIT.2021.3113921","volume":"67","author":"D Gamarnik","year":"2021","unstructured":"Gamarnik, D., K\u0131z\u0131lda\u011f, E.C., Zadik, I.: Inference in high-dimensional linear regression via lattice basis reduction and integer relation detection. IEEE Trans. Inf. Theory 67(12), 8109\u20138139 (2021)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"119_CR15","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s00454-023-00605-x","volume":"71","author":"I Gkioulekas","year":"2024","unstructured":"Gkioulekas, I., Gortler, S.J., Theran, L., Zickler, T.: Trilateration using unlabeled path or loop lengths. Discret. Comput. Geom. 71(2), 399\u2013441 (2024). https:\/\/doi.org\/10.1007\/s00454-023-00605-x","journal-title":"Discret. Comput. Geom."},{"issue":"4","key":"119_CR16","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1353\/ajm.0.0132","volume":"132","author":"SJ Gortler","year":"2010","unstructured":"Gortler, S.J., Healy, A.D., Thurston, D.P.: Characterizing generic global rigidity. Am. J. Math. 132(4), 897\u2013939 (2010). https:\/\/doi.org\/10.1353\/ajm.0.0132","journal-title":"Am. J. Math."},{"key":"119_CR17","unstructured":"Gortler, S.J., Theran.: Lattices without a big constant and with noise. (2022). arXiv:2204.12340"},{"key":"119_CR18","volume-title":"Forum of Mathematics, Sigma","author":"SJ Gortler","year":"2019","unstructured":"Gortler, S.J., Theran, L., Thurston, D.P.: Generic unlabeled global rigidity. In: Kirby, R. (ed.) Forum of Mathematics, Sigma, vol. 7. Cambridge University Press, Cambridge (2019)"},{"issue":"1","key":"119_CR19","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/0221008","volume":"21","author":"B Hendrickson","year":"1992","unstructured":"Hendrickson, B.: Conditions for unique graph realizations. SIAM J. Comput. 21(1), 65\u201384 (1992). https:\/\/doi.org\/10.1137\/0221008","journal-title":"SIAM J. Comput."},{"issue":"1","key":"119_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jctb.2004.11.002","volume":"94","author":"B Jackson","year":"2005","unstructured":"Jackson, B., Jord\u00e1n, T.: Connected rigidity matroids and unique realizations of graphs. J. Comb. Theory Ser. B 94(1), 1\u201329 (2005). https:\/\/doi.org\/10.1016\/j.jctb.2004.11.002","journal-title":"J. Comb. Theory Ser. B"},{"issue":"7084","key":"119_CR21","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1038\/nature04556","volume":"440","author":"P Juh\u00e1s","year":"2006","unstructured":"Juh\u00e1s, P., Cherba, D., Duxbury, P., Punch, W., Billinge, S.: Ab initio determination of solid-state nanostructure. Nature 440(7084), 655\u2013658 (2006)","journal-title":"Nature"},{"issue":"1","key":"119_CR22","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"JC Lagarias","year":"1985","unstructured":"Lagarias, J.C., Odlyzko, A.M.: Solving low-density subset sum problems. J. Assoc. Comput. Mach. 32(1), 229\u2013246 (1985). https:\/\/doi.org\/10.1145\/2455.2461","journal-title":"J. Assoc. Comput. Mach."},{"key":"119_CR23","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/978-3-642-55566-4_27","volume-title":"Discrete and Computational Geometry","author":"P Lemke","year":"2003","unstructured":"Lemke, P., Skiena, S.S., Smith, W.D.: Reconstructing sets from interpoint distances. In: Lemke, P., Skiena, S.S., Smith, W.D. (eds.) Discrete and Computational Geometry, pp. 597\u2013631. Springer, Berlin (2003)"},{"issue":"4","key":"119_CR24","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Jr., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534 (1982). https:\/\/doi.org\/10.1007\/BF01457454","journal-title":"Math. Ann."},{"key":"119_CR25","doi-asserted-by":"publisher","unstructured":"Lovasz, L.: Computing ears and branchings in parallel. In: 26th Annual Symposium on Foundations of Computer Science (SFCS 1985), pp. 464\u2013467. (1985). https:\/\/doi.org\/10.1109\/SFCS.1985.16","DOI":"10.1109\/SFCS.1985.16"},{"key":"119_CR26","first-page":"871","volume-title":"Graph Theory, Combinatorics, and Applications","author":"B Mohar","year":"1991","unstructured":"Mohar, B.: The Laplacian spectrum of graphs. In: Alvi, Y., Chartrand, G., Oellermann, O.R., Schwenk, A.J. (eds.) Graph Theory, Combinatorics, and Applications, vol. 2, pp. 871\u2013898. Wiley, Hoboken (1991)"},{"key":"119_CR27","doi-asserted-by":"crossref","unstructured":"Nguyen, P.Q., Stehl\u00e9, D.: LLL on the average. In: International Algorithmic Number Theory Symposium. Springer, pp. 238\u2013256 (2006)","DOI":"10.1007\/11792086_18"},{"key":"119_CR28","doi-asserted-by":"publisher","first-page":"94215","DOI":"10.1109\/ACCESS.2019.2928130","volume":"7","author":"LT Nguyen","year":"2019","unstructured":"Nguyen, L.T., Kim, J., Shim, B.: Low-rank matrix completion: a contemporary survey. IEEE Access 7, 94215\u201394237 (2019). https:\/\/doi.org\/10.1109\/ACCESS.2019.2928130","journal-title":"IEEE Access"},{"key":"119_CR29","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001","volume-title":"Matroid Theory, volume\u00a021 of Oxford Graduate Texts in Mathematics","author":"J Oxley","year":"2011","unstructured":"Oxley, J.: Matroid Theory, volume\u00a021 of Oxford Graduate Texts in Mathematics, second Oxford University Press, Oxford (2011). https:\/\/doi.org\/10.1093\/acprof:oso\/9780198566946.001.0001","edition":"second"},{"key":"119_CR30","unstructured":"Saxe, J.B.: Embeddability of weighted graphs in $$k$$-space is strongly NP-hard. In: Proceedings of the 17th Allerton Conference in Communications, Control and Computing, pp. 480\u2013489 (1979)"},{"issue":"1","key":"119_CR31","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF02579179","volume":"1","author":"PD Seymour","year":"1981","unstructured":"Seymour, P.D.: Recognizing graphic matroids. Combinatorica 1(1), 75\u201378 (1981). https:\/\/doi.org\/10.1007\/BF02579179","journal-title":"Combinatorica"},{"issue":"2","key":"119_CR32","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/S0092-8240(05)80259-9","volume":"56","author":"SS Skiena","year":"1994","unstructured":"Skiena, S.S., Sundaram, G.: A partial digest approach to restriction site mapping. Bull. Math. Biol. 56(2), 275\u2013294 (1994)","journal-title":"Bull. Math. Biol."},{"key":"119_CR33","doi-asserted-by":"crossref","unstructured":"So, A.M.-C., Ye, Y.: A semidefinite programming approach to tensegrity theory and realizability of graphs. In: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. Society for Industrial and Applied Mathematics. pp. 766\u2013775 (2006)","DOI":"10.1145\/1109557.1109641"},{"key":"119_CR34","first-page":"29602","volume":"34","author":"MJ Song","year":"2021","unstructured":"Song, M.J., Zadik, I., Bruna, J.: On the cryptographic hardness of learning single periodic neurons. Adv. Neural. Inf. Process. Syst. 34, 29602\u201329615 (2021)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"119_CR35","doi-asserted-by":"publisher","first-page":"905","DOI":"10.2307\/2034435","volume":"11","author":"WT Tutte","year":"1960","unstructured":"Tutte, W.T.: An algorithm for determining whether a given binary matroid is graphic. Proc. Am. Math. Soc. 11, 905\u2013917 (1960). https:\/\/doi.org\/10.2307\/2034435","journal-title":"Proc. Am. Math. Soc."},{"issue":"3","key":"119_CR36","doi-asserted-by":"publisher","first-page":"509","DOI":"10.2307\/2371182","volume":"57","author":"H Whitney","year":"1935","unstructured":"Whitney, H.: On the abstract properties of linear dependence. Am. J. Math. 57(3), 509\u2013533 (1935). https:\/\/doi.org\/10.2307\/2371182","journal-title":"Am. J. Math."},{"issue":"1\u20134","key":"119_CR37","doi-asserted-by":"publisher","first-page":"245","DOI":"10.2307\/2371127","volume":"55","author":"H Whitney","year":"1933","unstructured":"Whitney, H.: 2-Isomorphic graphs. Am. J. Math. 55(1\u20134), 245\u2013254 (1933). https:\/\/doi.org\/10.2307\/2371127","journal-title":"Am. J. Math."},{"key":"119_CR38","unstructured":"Zadik, I., Song, M.J., Wein, A.S., Bruna, J.: Lattice-based methods surpass sum-of-squares in clustering. In P.-L. Loh, M.\u00a0Raginsky (eds) Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 1247\u20131248. PMLR, 02\u201305 Jul 2022. arXiv:2112.03898"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00119-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-024-00119-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00119-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,15]],"date-time":"2024-11-15T14:03:33Z","timestamp":1731679413000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-024-00119-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,11]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["119"],"URL":"https:\/\/doi.org\/10.1007\/s00493-024-00119-x","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,11]]},"assertion":[{"value":"25 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 June 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}