{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T07:06:25Z","timestamp":1742972785310,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031826962"},{"type":"electronic","value":"9783031826979"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-82697-9_22","type":"book-chapter","created":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T10:17:42Z","timestamp":1739614662000},"page":"298-310","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Holey Graphs: Very Large Betti Numbers are Testable"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6323-9452","authenticated-orcid":false,"given":"D\u00e1niel","family":"Szab\u00f3","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3823-6804","authenticated-orcid":false,"given":"Simon","family":"Apers","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,16]]},"reference":[{"issue":"1","key":"22_CR1","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/jagm.1994.1005","volume":"16","author":"N Alon","year":"1994","unstructured":"Alon, N., Duke, R.A., Lefmann, H., Rodl, V., Yuster, R.: The algorithmic aspects of the regularity lemma. J. Algorithms 16(1), 80\u2013109 (1994). https:\/\/doi.org\/10.1006\/jagm.1994.1005","journal-title":"J. Algorithms"},{"key":"22_CR2","doi-asserted-by":"publisher","unstructured":"Alon, N., Shapira, A.: Every monotone graph property is testable. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 128\u2013137 (2005). https:\/\/doi.org\/10.1145\/1060590.1060611","DOI":"10.1145\/1060590.1060611"},{"issue":"6","key":"22_CR3","doi-asserted-by":"publisher","first-page":"1703","DOI":"10.1137\/06064888X","volume":"37","author":"N Alon","year":"2008","unstructured":"Alon, N., Shapira, A.: A characterization of the (natural) graph properties testable with one-sided error. SIAM J. Comput. 37(6), 1703\u20131727 (2008). https:\/\/doi.org\/10.1137\/06064888X","journal-title":"SIAM J. Comput."},{"key":"22_CR4","doi-asserted-by":"publisher","unstructured":"Apers, S., Gribling, S., Sen, S., Szab\u00f3, D.: A (simple) classical algorithm for estimating Betti numbers. Quantum 7, 1202 (2023). https:\/\/doi.org\/10.22331\/q-2023-12-06-1202","DOI":"10.22331\/q-2023-12-06-1202"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"010319","DOI":"10.1103\/PRXQuantum.5.010319","volume":"5","author":"DW Berry","year":"2024","unstructured":"Berry, D.W., et al.: Analyzing prospects for quantum advantage in topological data analysis. PRX Quantum 5, 010319 (2024). https:\/\/doi.org\/10.1103\/PRXQuantum.5.010319","journal-title":"PRX Quantum"},{"key":"22_CR6","doi-asserted-by":"publisher","unstructured":"Bukkuri, A., Andor, N., Darcy, I.K.: Applications of topological data analysis in oncology. Front. Artif. Intell. 4 (2021). https:\/\/doi.org\/10.3389\/frai.2021.659037","DOI":"10.3389\/frai.2021.659037"},{"key":"22_CR7","unstructured":"Chazal, F., Fasy, B., Lecci, F., Michel, B., Rinaldo, A., Wasserman, L.: Subsampling methods for persistent homology. In: Bach, F., Blei, D. (eds.) Proceedings of the 32nd International Conference on Machine Learning. Proceedings of Machine Learning Research, vol.\u00a037, pp. 2143\u20132151. PMLR, Lille, France (2015). https:\/\/proceedings.mlr.press\/v37\/chazal15.html"},{"issue":"25","key":"22_CR8","first-page":"1219","volume":"286","author":"R Cordovil","year":"1978","unstructured":"Cordovil, R.: Sur les g\u00e9ometries simpliciales. C. R. Hebd. Seances Acad. Sci. 286(25), 1219\u20131222 (1978)","journal-title":"C. R. Hebd. Seances Acad. Sci."},{"key":"22_CR9","doi-asserted-by":"publisher","unstructured":"Cordovil, R., Lindstr\u00f6m, B.: Simplicial matroids. In: Combinatorial Geometries. Cambridge University Press (1987). https:\/\/doi.org\/10.1017\/CBO9781107325715","DOI":"10.1017\/CBO9781107325715"},{"issue":"2","key":"22_CR10","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1002\/sapm1970492109","volume":"49","author":"HH Crapo","year":"1970","unstructured":"Crapo, H.H., Rota, G.C.: On the foundations of combinatorial theory II. Combinatorial geometries. Stud. Appl. Math. 49(2), 109\u2013133 (1970). https:\/\/doi.org\/10.1002\/sapm1970492109","journal-title":"Stud. Appl. Math."},{"key":"22_CR11","doi-asserted-by":"publisher","unstructured":"Crichigno, M., Kohler, T.: Clique homology is QMA1-hard. Nat. Commun. 15 (2024). https:\/\/doi.org\/10.1038\/s41467-024-54118-z","DOI":"10.1038\/s41467-024-54118-z"},{"key":"22_CR12","doi-asserted-by":"publisher","unstructured":"Elek, G.: Betti Numbers are Testable, pp. 139\u2013149. Springer Berlin Heidelberg Berlin, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13580-4_6","DOI":"10.1007\/978-3-642-13580-4_6"},{"key":"22_CR13","doi-asserted-by":"publisher","unstructured":"Fischer, E., Newman, I.: Testing versus estimation of graph properties. SIAM J. Comput. 37(2), 482\u2013501 (2007). https:\/\/doi.org\/10.1137\/060652324","DOI":"10.1137\/060652324"},{"key":"22_CR14","doi-asserted-by":"publisher","unstructured":"Fox, J.: A new proof of the graph removal lemma. Ann. Math. 174, 561\u2013579 (2011). https:\/\/doi.org\/10.4007\/annals.2011.174.1.17","DOI":"10.4007\/annals.2011.174.1.17"},{"key":"22_CR15","doi-asserted-by":"publisher","unstructured":"F\u00fcredi, Z.: Extremal hypergraphs and combinatorial geometry. In: Proceedings of the International Congress of Mathematicians, pp. 1343\u20131352. Birkh\u00e4user Basel (1995). https:\/\/doi.org\/10.1007\/978-3-0348-9078-6_129","DOI":"10.1007\/978-3-0348-9078-6_129"},{"key":"22_CR16","doi-asserted-by":"publisher","unstructured":"Goldreich, O.: Introduction to testing graph properties. In: Goldreich, O. (eds.) Property Testing: Current Research and Surveys, pp. 105\u2013141 (2010). https:\/\/doi.org\/10.1007\/978-3-642-16367-8","DOI":"10.1007\/978-3-642-16367-8"},{"key":"22_CR17","doi-asserted-by":"publisher","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653\u2013750 (1998). https:\/\/doi.org\/10.1145\/285055.285060","DOI":"10.1145\/285055.285060"},{"key":"22_CR18","doi-asserted-by":"publisher","unstructured":"Gyurik, C., Cade, C., Dunjko, V.: Towards quantum advantage via topological data analysis. Quantum 6, 855 (2022). https:\/\/doi.org\/10.22331\/q-2022-11-10-855","DOI":"10.22331\/q-2022-11-10-855"},{"key":"22_CR19","doi-asserted-by":"publisher","unstructured":"Hayakawa, R.: Quantum algorithm for persistent Betti numbers and topological data analysis. Quantum 6, 873 (2022). https:\/\/doi.org\/10.22331\/q-2022-12-07-873","DOI":"10.22331\/q-2022-12-07-873"},{"issue":"1","key":"22_CR20","doi-asserted-by":"publisher","first-page":"8888","DOI":"10.1038\/s41598-021-88027-8","volume":"11","author":"AS Krishnapriyan","year":"2021","unstructured":"Krishnapriyan, A.S., Montoya, J., Haranczyk, M., Hummelsh\u00f8j, J., Morozov, D.: Machine learning with persistent homology and chemical word embeddings improves prediction accuracy and interpretability in metal-organic frameworks. Sci. Rep. 11(1), 8888 (2021). https:\/\/doi.org\/10.1038\/s41598-021-88027-8","journal-title":"Sci. Rep."},{"issue":"1","key":"22_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/ncomms10138","volume":"7","author":"S Lloyd","year":"2016","unstructured":"Lloyd, S., Garnerone, S., Zanardi, P.: Quantum algorithms for topological and geometric analysis of data. Nat. Commun. 7(1), 1\u20137 (2016). https:\/\/doi.org\/10.1038\/ncomms10138","journal-title":"Nat. Commun."},{"key":"22_CR22","unstructured":"Nanda, V.: Computational algebraic topology lecture notes. https:\/\/people.maths.ox.ac.uk\/nanda\/cat\/TDANotes.pdf"},{"issue":"4","key":"22_CR23","doi-asserted-by":"publisher","first-page":"4281","DOI":"10.1093\/mnras\/stw2862","volume":"465","author":"P Pranav","year":"2016","unstructured":"Pranav, P., et al.: The topology of the cosmic web in terms of persistent Betti numbers. Mon. Not. R. Astron. Soc. 465(4), 4281\u20134310 (2016). https:\/\/doi.org\/10.1093\/mnras\/stw2862","journal-title":"Mon. Not. R. Astron. Soc."},{"key":"22_CR24","unstructured":"Szemer\u00e9di, E.: Regular partitions of graphs. In: Probl\u00e8mes combinatoires et th\u00e9orie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, vol.\u00a0260, pp. 399\u2013401. CNRS, Paris (1978)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2025: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-82697-9_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T10:17:50Z","timestamp":1739614670000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-82697-9_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031826962","9783031826979"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-82697-9_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"16 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bratislava","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sofsem.sk","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}