{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T12:53:51Z","timestamp":1765371231636,"version":"3.46.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T00:00:00Z","timestamp":1764028800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T00:00:00Z","timestamp":1764028800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P 29984-N35","P 29984-N35","W1230"],"award-info":[{"award-number":["P 29984-N35","P 29984-N35","W1230"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008332","name":"Graz University of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008332","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Appl. and Comput. Topology"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We study the algorithmic complexity of computing the persistence barcode of a randomly generated filtration. We provide a general technique to bound the expected complexity of reducing the boundary matrix in terms of the density of its reduced form. We apply this technique finding upper bounds for the average fill-in (number of non-zero entries) of the boundary matrix on \u010cech, Vietoris\u2013Rips and Erd\u0151s\u2013R\u00e9nyi filtrations after matrix reduction, thus obtaining bounds on the expected complexity of the barcode computation. Our method is based on previous results on the expected Betti numbers of the corresponding complexes. Our fill-in bounds for \u010cech and Vietoris\u2013Rips complexes are asymptotically tight up to a logarithmic factor. In particular, both our fill-in and computation bounds are better than the worst-case estimates. We also provide an Erd\u0151s\u2013R\u00e9nyi filtration realizing the worst-case fill-in and computation.<\/jats:p>","DOI":"10.1007\/s41468-025-00218-8","type":"journal-article","created":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T14:02:09Z","timestamp":1764079329000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Expected Complexity of Barcode Reduction"],"prefix":"10.1007","volume":"9","author":[{"given":"Barbara","family":"Giunti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Houry","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kerber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"S\u00f6ls","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,11,25]]},"reference":[{"key":"218_CR1","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-662-44199-2_23","volume":"8592","author":"H Adams","year":"2014","unstructured":"Adams, H., Tausz, A., Vejdemo-Johansson, M.: JavaPlex: A research software package for persistent (co)homology\u2019. Mathematical Software - ICMS 2014. Lect. Notes Comput. Sc. 8592, 129\u2013136 (2014). https:\/\/doi.org\/10.1007\/978-3-662-44199-2_23","journal-title":"Lect. Notes Comput. Sc."},{"key":"218_CR2","doi-asserted-by":"publisher","unstructured":"Alonso, \u00c1J., Kerber, M.: \u201cDecomposition of Zero-Dimensional Persistence Modules via Rooted Subsets\u201d. In: 39th International Symposium on Computational Geometry (SoCG). (2023) https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2023.7","DOI":"10.4230\/LIPIcs.SoCG.2023.7"},{"key":"218_CR3","doi-asserted-by":"publisher","unstructured":"Alonso, \u00c1J., Kerber, M., Skraba, P.: \u201cProbabilistic Analysis of Multiparameter Persistence Decompositions into Intervals\u201d. In: 40th International Symposium on Computational Geometry (SoCG) (2024). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2024.6","DOI":"10.4230\/LIPIcs.SoCG.2024.6"},{"key":"218_CR4","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s41468-021-00071-5","volume":"5","author":"U Bauer","year":"2021","unstructured":"Bauer, U.: Ripser: efficient computation of Vietoris-Rips persistence barcodes. J Appl. and Comput. Topology 5, 391\u2013423 (2021). https:\/\/doi.org\/10.1007\/s41468-021-00071-5","journal-title":"J Appl. and Comput. Topology"},{"key":"218_CR5","doi-asserted-by":"publisher","unstructured":"Bauer, U., Masood, TB., Giunti, B., Houry, G., Kerber, M., Rathod, A.: \u201cKeeping it sparse: Computing Persistent Homology revisited\u201d. In: Computing in Geometry and Topology 3.1, 6:1\u20136:26 (2024). https:\/\/doi.org\/10.57717\/cgt.v3i1.50","DOI":"10.57717\/cgt.v3i1.50"},{"key":"218_CR6","doi-asserted-by":"publisher","unstructured":"Bauer, U., Edelsbrunner, H.: \u201cThe Morse Theory of \u00c4 &OElig;ech and Delaunay Filtrations\u201d. In: 30th Annual Symposium on Computational Geometry (SoCG) (2014). https:\/\/doi.org\/10.1145\/2582112.2582167","DOI":"10.1145\/2582112.2582167"},{"key":"218_CR7","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jsc.2016.03.008","volume":"78","author":"U Bauer","year":"2017","unstructured":"Bauer, U., Kerber, M., Reininghaus, J., Wagner, H.: Phat-Persistent Homology Algorithms Toolbox. J. Symb. Comput. 78, 76\u201390 (2017). https:\/\/doi.org\/10.1016\/j.jsc.2016.03.008","journal-title":"J. Symb. Comput."},{"key":"218_CR8","doi-asserted-by":"publisher","unstructured":"Bauer, U., Roll, F.: \u201cGromov Hyperbolicity, Geodesic Defect, and Apparent Pairs in Vietoris-Rips Filtrations\u201d. In: 38th International Symposium on Computational Geometry (SoCG) (2022). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2022.15","DOI":"10.4230\/LIPIcs.SoCG.2022.15"},{"key":"218_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04245-8","author":"M de Berg","year":"2000","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Cheong, O.: Computational Geometry: Algorithms and Applications. Springer, Berlin, Heidelberg. (2000). https:\/\/doi.org\/10.1007\/978-3-662-04245-8","journal-title":"Springer, Berlin, Heidelberg."},{"key":"218_CR10","unstructured":"Bj\u00f6rner, A.:. \u201cTopological Methods\u201d. In: Handbook of Combinatorics (Vol. 2). Ed. by L.\u00a0Lov\u00e1sz R.\u00a0L.\u00a0Graham M.\u00a0Gr\u00f6tschel. MIT Press, Cambridge, MA, USA, pp.\u00a01819\u20131872 (1996)"},{"key":"218_CR11","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s41468-017-0010-0","volume":"1","author":"O Bobrowski","year":"2018","unstructured":"Bobrowski, O., Kahle, M.: Topology of random geometric complexes: a survey. J Appl. and Comput. Topology 1, 331\u2013364 (2018). https:\/\/doi.org\/10.1007\/s41468-017-0010-0","journal-title":"J Appl. and Comput. Topology"},{"key":"218_CR12","doi-asserted-by":"publisher","first-page":"2032","DOI":"10.1214\/16-AAP1232","volume":"27","author":"O Bobrowski","year":"2017","unstructured":"Bobrowski, O., Kahle, M., Skraba, P.: Maximally persistent cycles in random geometric complexes. Ann. Appl. Probab. 27, 2032\u20132060 (2017). https:\/\/doi.org\/10.1214\/16-AAP1232","journal-title":"Ann. Appl. Probab."},{"key":"218_CR13","doi-asserted-by":"publisher","unstructured":"Chach\u00f3lski, W., Giunti, B., Jin, A., Landi, C.: \u201cDecomposing filtered chain complexes: Geometry behind barcoding algorithms\u201d. In: Comp. Geom.:Theor. Appl.109 (2023). https:\/\/doi.org\/10.1016\/j.comgeo.2022.101938","DOI":"10.1016\/j.comgeo.2022.101938"},{"key":"218_CR14","doi-asserted-by":"publisher","unstructured":"Chang, D.R., Donald, BR.: \u201cOn the complexity of computing the homology type of a triangulation\u201d. In: 32nd Annual Symp. Foundations Comput. Sci. (STOC) (1991). https:\/\/doi.org\/10.1109\/SFCS.1991.185432","DOI":"10.1109\/SFCS.1991.185432"},{"key":"218_CR15","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.comgeo.2012.02.010","volume":"46","author":"C Chen","year":"2013","unstructured":"Chen, C., Kerber, M.: \u201cAn output-sensitive algorithm for persistent homology\u2019\u2019. In: Comp. Geom.:Theor. Appl. 46, 435\u2013447 (2013). https:\/\/doi.org\/10.1016\/j.comgeo.2012.02.010","journal-title":"Appl."},{"key":"218_CR16","doi-asserted-by":"crossref","unstructured":"Delgado-Friedrichs, O., Robins, V., Sheppard, A.: \u201cSkeletonization and Partitioning of Digital Images Using Discrete Morse Theory\u201d. In: IEEE Trans Pattern Anal Mach Intel 37 (2015)","DOI":"10.1109\/TPAMI.2014.2346172"},{"key":"218_CR17","doi-asserted-by":"publisher","first-page":"229","DOI":"10.4310\/JOC.2013.v4.n2.a4","volume":"4","author":"B Demarco","year":"2013","unstructured":"Demarco, B., Hamm, A., Kahn, J.: On the triangle space of a random graph. J. Comb. 4, 229\u2013249 (2013). https:\/\/doi.org\/10.4310\/JOC.2013.v4.n2.a4","journal-title":"J. Comb."},{"key":"218_CR18","doi-asserted-by":"publisher","unstructured":"Divol, V., Chazal, F.: \u201cThe density of expected persistence diagrams and its kernel based estimation\u201d. In: J. Comp. Geom.10, pp.\u00a0127\u2013153 (2019).. https:\/\/doi.org\/10.20382\/jocg.v10i2a7","DOI":"10.20382\/jocg.v10i2a7"},{"key":"218_CR19","unstructured":"Giunti, B.,, Lazovskis, J., Rieck, B.: DONUT: Database of Original & Non-Theoretical Uses of Topology (2022). https:\/\/donut.topology.rocks"},{"key":"218_CR20","volume-title":"Direct Methods for Sparse Matrices","author":"IS Duff","year":"1986","unstructured":"Duff, I.S., Erisman, A.M., Reid, J.K.: Direct Methods for Sparse Matrices. Oxford University Press, Oxford (1986)"},{"key":"218_CR21","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/069","author":"H Edelsbrunner","year":"2010","unstructured":"Edelsbrunner, H., Harer, J.: Computational topology: an introduction. American Mathematical Society, Providence, RI. (2010). https:\/\/doi.org\/10.1090\/mbk\/069","journal-title":"American Mathematical Society, Providence, RI."},{"key":"218_CR22","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s00454-002-2885-2","volume":"28","author":"H Edelsbrunner","year":"2002","unstructured":"Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological Persistence and Simplification. Discrete. Comput. Geom. 28, 511\u2013533 (2002). https:\/\/doi.org\/10.1007\/s00454-002-2885-2","journal-title":"Discrete. Comput. Geom."},{"key":"218_CR23","unstructured":"Forman, R.:\u201cA user\u2019s guide to discrete Morse theory\u201d. In: Seminaire Lotharinigien de Combinatoire48 (2002)"},{"key":"218_CR24","doi-asserted-by":"publisher","unstructured":"Giunti, B., Houry, G., Kerber, M.: \u201cAverage Complexity of Matrix Reduction for Clique Filtrations\u201d. In: Proc. Int. Symp. Symb. Alg. Comp. (ISSAC) (2022). https:\/\/doi.org\/10.1145\/3476446.3535474","DOI":"10.1145\/3476446.3535474"},{"key":"218_CR25","doi-asserted-by":"publisher","first-page":"1897","DOI":"10.1109\/TVCG.2023.3238008","volume":"30","author":"P Guillou","year":"2024","unstructured":"Guillou, P., Vidal, J., Tierny, J.: Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data - An Algorithm and a Benchmark. IEEE Trans. Vis. Comput. Graph. 30, 1897\u20131915 (2024). https:\/\/doi.org\/10.1109\/TVCG.2023.3238008","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"218_CR26","unstructured":"Henselman-Petrusek, G., Ghrist, R.: \u201cMatroid filtrations and computational persistent homology\u201d. In: arXiv preprint 1606.00199 (2016)"},{"key":"218_CR27","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1109\/TCT.1972.1083477","volume":"19","author":"H Hsieh","year":"1972","unstructured":"Hsieh, H., Ghausi, M.: A probabilistic approach to optimal pivoting and prediction of fill-in for random sparse matrices. IEEE T. Circuit Theory 19, 329\u2013336 (1972). https:\/\/doi.org\/10.1109\/TCT.1972.1083477","journal-title":"IEEE T. Circuit Theory"},{"key":"218_CR28","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718","author":"S Janson","year":"2000","unstructured":"Janson, S., Luczak, T., Rucinski, A.: Random Graphs. Wiley, New York. (2000). https:\/\/doi.org\/10.1002\/9781118032718","journal-title":"Wiley, New York."},{"key":"218_CR29","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1111\/j.1467-9574.1980.tb00681.x","volume":"34","author":"R Kaas","year":"1980","unstructured":"Kaas, R., Buhrman, J.M.: Mean, median and mode in binomial distributions. Stat. Neerl. 34, 13\u201318 (1980). https:\/\/doi.org\/10.1111\/j.1467-9574.1980.tb00681.x","journal-title":"Stat. Neerl."},{"key":"218_CR30","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s00454-010-9319-3","volume":"45","author":"M Kahle","year":"2011","unstructured":"Kahle, M.: Random Geometric Complexes. Discrete & Computational Geometry 45, 553\u2013573 (2011). https:\/\/doi.org\/10.1007\/s00454-010-9319-3","journal-title":"Discrete & Computational Geometry"},{"key":"218_CR31","doi-asserted-by":"publisher","unstructured":"Kahle, M.: Sharp vanishing thresholds for cohomology of random flag complexes. Ann. Math. 179, 1085\u20131107 (2014). https:\/\/doi.org\/10.4007\/annals.2014.179.3.5","DOI":"10.4007\/annals.2014.179.3.5"},{"key":"218_CR32","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1090\/conm\/620\/12367","volume":"620","author":"M Kahle","year":"2014","unstructured":"Kahle, M.: Topology of random simplicial complexes: a survey. AMS Contemp. Vol. Math. 620, 201\u2013221 (2014)","journal-title":"AMS Contemp. Vol. Math."},{"key":"218_CR33","unstructured":"Kerber, M., Schreiber, H.: \u201cOn the expected complexity of matrix reduction for random complexes\u201d. In: Computer Algebra in Scientific Computing (CASC 2020). Extended abstract (2020)"},{"key":"218_CR34","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-662-44199-2_28","volume":"8592","author":"C Maria","year":"2014","unstructured":"Maria, C., Boissonnat, J.-D., Glisse, M., Yvinec, M.: \u201cThe GUDHI library: Simplicial complexes and persistent homology\u2019\u2019. In: Mathematical Software - ICMS 2014. Lect. Notes Comput. Sc. 8592, 167\u2013174 (2014). https:\/\/doi.org\/10.1007\/978-3-662-44199-2_28","journal-title":"Lect. Notes Comput. Sc."},{"key":"218_CR35","doi-asserted-by":"publisher","unstructured":"Milosavljevi\u0107, N., Morozov, D., Skraba, P.: \u201cZigzag Persistent Homology in Matrix Multiplication Time\u201d. In: 27th Annual Symposium on Computational Geometry (SoCG), pp.\u00a0216\u2013225 (2011). https:\/\/doi.org\/10.1145\/1998196.1998229","DOI":"10.1145\/1998196.1998229"},{"key":"218_CR36","doi-asserted-by":"crossref","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN: 9780521835404 (2005). https:\/\/books.google.com\/books?id=0bAYl6d7hvkC","DOI":"10.1017\/CBO9780511813603"},{"key":"218_CR37","unstructured":"Morozov, D.: \u201cPersistence algorithm takes cubic time in worst case\u201d. In: BioGeometry News, Dept. Comput. Sci., Duke Univ 2 (2005)"},{"key":"218_CR38","unstructured":"Morozov, D.: Dionysus, a C++ library for computing persistent homology (2010). URL: mrzv.org\/software\/dionysus"},{"key":"218_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1140\/epjds\/s13688-017-0109-5","volume":"6","author":"N Otter","year":"2017","unstructured":"Otter, N., Porter, M.A., Tillmann, U., Grindrod, P., Harrington, H.A.: A roadmap for the computation of persistent homology. EPJ Data Sci. 6, 1\u201338 (2017). https:\/\/doi.org\/10.1140\/epjds\/s13688-017-0109-5","journal-title":"EPJ Data Sci."},{"key":"218_CR40","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/209","volume-title":"Persistence theory: from quiver representations to data analysis","author":"SY Oudot","year":"2015","unstructured":"Oudot, S.Y.: Persistence theory: from quiver representations to data analysis. American Mathematical Society, Providence RI (2015)"},{"key":"218_CR41","unstructured":"P\u00e9rez, JB., Hauke, S., Lupo, U., Caorsi, M., Dassatti, A.: \u201cGiotto-ph: A Python Library for High-Performance Computation of Persistent Homology of Vietoris\u2013Rips Filtrations\u201d. In: arXiv preprint 2107.05412 (2021)"},{"key":"218_CR42","unstructured":"Schreiber, H.: \u201cAlgorithmic Aspects in standard and non-standard Persistent Homology\u201d. PhD thesis. Graz University of Technology (2019)"},{"key":"218_CR43","doi-asserted-by":"publisher","DOI":"10.1090\/stml\/090","volume-title":"Discrete Morse Theory","author":"NA Scoville","year":"2019","unstructured":"Scoville, N.A.: Discrete Morse Theory. American Mathematical Society, Providence, RI (2019)"},{"key":"218_CR44","doi-asserted-by":"publisher","unstructured":"Wagner, H.: \u201cSlice, Simplify and Stitch: Topology-Preserving Simplification Scheme for Massive Voxel Data\u201d. In: 39th International Symposium on Computational Geometry (SoCG) (2023). https:\/\/doi.org\/10.4230\/LIPICS.SOCG.2023.60","DOI":"10.4230\/LIPICS.SOCG.2023.60"}],"container-title":["Journal of Applied and Computational Topology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-025-00218-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41468-025-00218-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-025-00218-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T09:51:45Z","timestamp":1765360305000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41468-025-00218-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,25]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["218"],"URL":"https:\/\/doi.org\/10.1007\/s41468-025-00218-8","relation":{},"ISSN":["2367-1726","2367-1734"],"issn-type":[{"type":"print","value":"2367-1726"},{"type":"electronic","value":"2367-1734"}],"subject":[],"published":{"date-parts":[[2025,11,25]]},"assertion":[{"value":"11 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is none.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"29"}}