{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T12:33:57Z","timestamp":1765370037775,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T00:00:00Z","timestamp":1656892800000},"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 33765-N"],"award-info":[{"award-number":["P 33765-N"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Austrian Science Fund (FWF)","award":["P 29984-N35"],"award-info":[{"award-number":["P 29984-N35"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,4]]},"DOI":"10.1145\/3476446.3535474","type":"proceedings-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T13:16:01Z","timestamp":1657026961000},"page":"187-196","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Average Complexity of Matrix Reduction for Clique Filtrations"],"prefix":"10.1145","author":[{"given":"Barbara","family":"Giunti","sequence":"first","affiliation":[{"name":"Graz University of Technology, Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Houry","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique Palaiseau, Palaiseau, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kerber","sequence":"additional","affiliation":[{"name":"Graz University of Technology, Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44199-2_23"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41468-021-00071-5"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2016.03.008"},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the 38th Annual Symposium on Computational Geometry (SoCG '22)","author":"Bauer Ulrich","year":"2022","unstructured":"Ulrich Bauer and Fabian Roll . 2022 . Gromov hyperbolicity, geodesic defect, and apparent pairs in Vietoris-Rips filtrations . In Proceedings of the 38th Annual Symposium on Computational Geometry (SoCG '22) . Association for Computing Machinery, New York, NY, USA. Ulrich Bauer and Fabian Roll. 2022. Gromov hyperbolicity, geodesic defect, and apparent pairs in Vietoris-Rips filtrations. In Proceedings of the 38th Annual Symposium on Computational Geometry (SoCG '22). Association for Computing Machinery, New York, NY, USA."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41468-017-0010-0"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1214\/16-AAP1232"},{"key":"e_1_3_2_1_7_1","unstructured":"Wojciech Chach\u00f3lski Barbara Giunti Alvin Jin and Claudia Landi. 2020. Decomposing filtered chain complexes: geometry behind barcoding algorithms. Preprint arXiv:2012.01033.  Wojciech Chach\u00f3lski Barbara Giunti Alvin Jin and Claudia Landi. 2020. Decomposing filtered chain complexes: geometry behind barcoding algorithms. Preprint arXiv:2012.01033."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.02.010"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4310\/JOC.2013.v4.n2.a4"},{"key":"e_1_3_2_1_10_1","first-page":"127","article-title":"The density of expected persistence diagrams and its kernel based estimation","volume":"10","author":"Divol Vincent","year":"2019","unstructured":"Vincent Divol and Fr\u00e9 d\u00e9 ric Chazal . 2019 . The density of expected persistence diagrams and its kernel based estimation . Journal of Computational Geometry , Vol. 10 , 2 (2019), 127 -- 153 . Vincent Divol and Fr\u00e9 d\u00e9 ric Chazal. 2019. The density of expected persistence diagrams and its kernel based estimation. Journal of Computational Geometry, Vol. 10, 2 (2019), 127--153.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_3_2_1_11_1","volume-title":"Chang","author":"Donald Bruce R.","year":"1991","unstructured":"Bruce R. Donald and David R . Chang . 1991 . On the complexity of computing the homology type of a triangulation. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. IEEE, San Juan, PR, USA , 650--661. Bruce R. Donald and David R. Chang. 1991. On the complexity of computing the homology type of a triangulation. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. IEEE, San Juan, PR, USA, 650--661."},{"key":"e_1_3_2_1_12_1","volume-title":"Reid","author":"Duff Iain S.","year":"1986","unstructured":"Iain S. Duff , Albert M. Erisman , and John K . Reid . 1986 . Direct Methods for Sparse Matrices .Oxford University Press , Inc., USA. Iain S. Duff, Albert M. Erisman, and John K. Reid. 1986. Direct Methods for Sparse Matrices .Oxford University Press, Inc., USA."},{"volume-title":"Computational Topology - an Introduction","author":"Edelsbrunner Herbert","key":"e_1_3_2_1_13_1","unstructured":"Herbert Edelsbrunner and John Harer . 2010. Computational Topology - an Introduction . American Mathematical Society , Providence, RI . Herbert Edelsbrunner and John Harer. 2010. Computational Topology - an Introduction. American Mathematical Society, Providence, RI."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796607"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Barbara Giunti Guillaume Houry and Michael Kerber. 2021. Average complexity of matrix reduction for clique filtrations. Preprint arXiv:2111.02125.  Barbara Giunti Guillaume Houry and Michael Kerber. 2021. Average complexity of matrix reduction for clique filtrations. Preprint arXiv:2111.02125.","DOI":"10.1145\/3476446.3535474"},{"key":"e_1_3_2_1_16_1","unstructured":"Gregory Henselman and Robert Ghrist. 2016. Matroid filtrations and computational persistent homology. Preprint arXiv:1606.00199.  Gregory Henselman and Robert Ghrist. 2016. Matroid filtrations and computational persistent homology. Preprint arXiv:1606.00199."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1972.1083477"},{"key":"e_1_3_2_1_18_1","volume-title":"nski","author":"Janson Svante","year":"2000","unstructured":"Svante Janson , Tomasz Luczak , and Andrzej Ruci ` nski . 2000 . Random Graphs .John Wiley & Sons, Ltd , USA. Svante Janson, Tomasz Luczak, and Andrzej Ruci`nski. 2000. Random Graphs .John Wiley & Sons, Ltd, USA."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9574.1980.tb00681.x"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116271.3116498"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2014.179.3.5"},{"volume-title":"Algebraic topology: applications and new directions. Contemp. Math.","author":"Kahle Matthew","key":"e_1_3_2_1_22_1","unstructured":"Matthew Kahle . 2014b. Topology of random simplicial complexes: a survey . In Algebraic topology: applications and new directions. Contemp. Math. , Vol. 620 . American Mathematical Society , Providence, RI , 201--221. Matthew Kahle. 2014b. Topology of random simplicial complexes: a survey. In Algebraic topology: applications and new directions. Contemp. Math., Vol. 620. American Mathematical Society, Providence, RI, 201--221."},{"key":"e_1_3_2_1_23_1","unstructured":"Michael Kerber and Hannah Schreiber. 2020. On the expected complexity of matrix reduction for random complexes. In Computer Algebra in Scientific Computing (CASC). Extended abstract.  Michael Kerber and Hannah Schreiber. 2020. On the expected complexity of matrix reduction for random complexes. In Computer Algebra in Scientific Computing (CASC). Extended abstract."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998229"},{"key":"e_1_3_2_1_25_1","volume-title":"Dept. Comput. Sci., Duke Univ","volume":"2","author":"Morozov Dmitriy","year":"2005","unstructured":"Dmitriy Morozov . 2005 . Persistence algorithm takes cubic time in worst case. BioGeometry News , Dept. Comput. Sci., Duke Univ , Vol. 2 (2005). Dmitriy Morozov. 2005. Persistence algorithm takes cubic time in worst case. BioGeometry News, Dept. Comput. Sci., Duke Univ, Vol. 2 (2005)."},{"key":"e_1_3_2_1_26_1","unstructured":"Dmitriy Morozov. 2010. Dionysus Library for Computing Persistent Homology. Retrieved from mrzv.org\/software\/dionysus.  Dmitriy Morozov. 2010. Dionysus Library for Computing Persistent Homology. Retrieved from mrzv.org\/software\/dionysus."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjds\/s13688-017-0109-5"},{"volume-title":"Persistence theory: from quiver representations to data analysis","author":"Oudot Steve Y.","key":"e_1_3_2_1_28_1","unstructured":"Steve Y. Oudot . 2015. Persistence theory: from quiver representations to data analysis . Vol. 209 . American Mathematical Society , Providence, RI . Steve Y. Oudot. 2015. Persistence theory: from quiver representations to data analysis. Vol. 209. American Mathematical Society, Providence, RI."},{"key":"e_1_3_2_1_29_1","volume-title":"Giotto-ph: A Python Library for High-Performance Computation of Persistent Homology of Vietoris--Rips Filtrations. Preprint arXiv:2107.05412.","author":"P\u00e9rez Juli\u00e1n Burella","year":"2021","unstructured":"Juli\u00e1n Burella P\u00e9rez , Sydney Hauke , Umberto Lupo , Matteo Caorsi , and Alberto Dassatti . 2021 . Giotto-ph: A Python Library for High-Performance Computation of Persistent Homology of Vietoris--Rips Filtrations. Preprint arXiv:2107.05412. Juli\u00e1n Burella P\u00e9rez, Sydney Hauke, Umberto Lupo, Matteo Caorsi, and Alberto Dassatti. 2021. Giotto-ph: A Python Library for High-Performance Computation of Persistent Homology of Vietoris--Rips Filtrations. Preprint arXiv:2107.05412."},{"key":"e_1_3_2_1_30_1","unstructured":"Dominik Schimd. 2020. Code for generating doundary matrix of random filtration up to degree 1. Available at https:\/\/github.com\/Dominiksfp\/Bac-Programming.  Dominik Schimd. 2020. Code for generating doundary matrix of random filtration up to degree 1. Available at https:\/\/github.com\/Dominiksfp\/Bac-Programming."},{"key":"e_1_3_2_1_32_1","unstructured":"The GUDHI Project. 2015. GUDHI User and Reference Manual .GUDHI Editorial Board. http:\/\/gudhi.gforge.inria.fr\/doc\/latest\/  The GUDHI Project. 2015. GUDHI User and Reference Manual .GUDHI Editorial Board. http:\/\/gudhi.gforge.inria.fr\/doc\/latest\/"}],"event":{"name":"ISSAC '22: International Symposium on Symbolic and Algebraic Computation","sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"location":"Villeneuve-d'Ascq France","acronym":"ISSAC '22"},"container-title":["Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476446.3535474","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3476446.3535474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:47Z","timestamp":1750188647000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476446.3535474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,4]]},"references-count":31,"alternative-id":["10.1145\/3476446.3535474","10.1145\/3476446"],"URL":"https:\/\/doi.org\/10.1145\/3476446.3535474","relation":{},"subject":[],"published":{"date-parts":[[2022,7,4]]},"assertion":[{"value":"2022-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}