{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T18:09:36Z","timestamp":1764785376611,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031598340"},{"type":"electronic","value":"9783031598357"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-59835-7_30","type":"book-chapter","created":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T07:05:03Z","timestamp":1716275103000},"page":"405-417","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Algorithms for\u00a0Spectral Hypergraph Sparsification"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9519-2487","authenticated-orcid":false,"given":"Tasuku","family":"Soma","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8399-2564","authenticated-orcid":false,"given":"Kam Chuen","family":"Tung","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8919-8479","authenticated-orcid":false,"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,22]]},"reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N., Svensson, O., Trevisan, L.: New notions and constructions of sparsification for graphs and hypergraphs. In: Proceedings of the IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 910\u2013928 (2019)","DOI":"10.1109\/FOCS.2019.00059"},{"issue":"8","key":"30_CR2","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/2492007.2492029","volume":"56","author":"J Batson","year":"2013","unstructured":"Batson, J., Spielman, D.A., Srivastava, N., Teng, S.H.: Spectral sparsification of graphs: theory and algorithms. Commun. ACM 56(8), 87\u201394 (2013)","journal-title":"Commun. ACM"},{"key":"30_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"SP Boyd","year":"2004","unstructured":"Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"key":"30_CR4","unstructured":"Calandriello, D., Lazaric, A., Valko, M.: Analysis of Kelner and Levin graph sparsification algorithm for a streaming setting. arXiv (2016)"},{"issue":"3","key":"30_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3178123","volume":"65","author":"THH Chan","year":"2018","unstructured":"Chan, T.H.H., Louis, A., Tang, Z.G., Zhang, C.: Spectral properties of hypergraph laplacian and approximation algorithms. J. ACM 65(3), 1\u201348 (2018). https:\/\/doi.org\/10.1145\/3178123","journal-title":"J. ACM"},{"issue":"1","key":"30_CR6","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1080\/15427951.2006.10129115","volume":"3","author":"F Chung","year":"2006","unstructured":"Chung, F., Lu, L.: Concentration inequalities and martingale inequalities: a survey. Internet Math. 3(1), 79\u2013127 (2006)","journal-title":"Internet Math."},{"issue":"1","key":"30_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2020.v016a015","volume":"16","author":"MB Cohen","year":"2020","unstructured":"Cohen, M.B., Musco, C., Pachocki, J.: Online row sampling. Theory Comput. 16(1), 1\u201325 (2020). https:\/\/doi.org\/10.4086\/toc.2020.v016a015","journal-title":"Theory Comput."},{"key":"30_CR8","doi-asserted-by":"crossref","unstructured":"Jambulapati, A., Lee, J.R., Liu, Y.P., Sidford, A.: Sparsifying sums of norms. arXiv (2023)","DOI":"10.1109\/FOCS57990.2023.00119"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Jambulapati, A., Liu, Y.P., Sidford, A.: Chaining, group leverage score overestimates, and fast spectral hypergraph sparsification. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pp. 196\u2013206 (2023)","DOI":"10.1145\/3564246.3585136"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Krauthgamer, R., Tardos, J., Yoshida, Y.: Towards tight bounds for spectral sparsification of hypergraphs. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 598\u2013611 (2021)","DOI":"10.1145\/3406325.3451061"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Krauthgamer, R., Tardos, J., Yoshida, Y.: Spectral hypergraph sparsifiers of nearly linear size. In: Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1159\u20131170 (2022)","DOI":"10.1109\/FOCS52979.2021.00114"},{"issue":"1","key":"30_CR12","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/141002281","volume":"46","author":"M Kapralov","year":"2017","unstructured":"Kapralov, M., Lee, Y.T., Musco, C., Musco, C.P., Sidford, A.: Single pass spectral sparsification in dynamic streams. SIAM J. Comput. 46(1), 456\u2013477 (2017)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"30_CR13","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s00224-012-9396-1","volume":"53","author":"JA Kelner","year":"2013","unstructured":"Kelner, J.A., Levin, A.: Spectral sparsification in the semi-streaming setting. Theory Comput. Syst. 53(2), 243\u2013262 (2013)","journal-title":"Theory Comput. Syst."},{"key":"30_CR14","doi-asserted-by":"crossref","unstructured":"Lee, J.R.: Spectral hypergraph sparsification via chaining. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 207\u2013218 (2023)","DOI":"10.1145\/3564246.3585165"},{"key":"30_CR15","unstructured":"Oko, K., Sakaue, S., Tanigawa, S.: Nearly tight spectral sparsification of directed hypergraphs. In: The Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP) (2023)"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"Rafiey, A., Yoshida, Y.: Sparsification of decomposable submodular functions. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol.\u00a036, pp. 10336\u201310344 (2022)","DOI":"10.1609\/aaai.v36i9.21275"},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Soma, T., Yoshida, Y.: Spectral sparsification of hypergraphs. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2570\u20132581. SIAM (2019)","DOI":"10.1137\/1.9781611975482.159"},{"issue":"6","key":"30_CR18","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1137\/080734029","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. SIAM J. Comput. 40(6), 1913\u20131926 (2011). https:\/\/doi.org\/10.1137\/080734029","journal-title":"SIAM J. Comput."},{"issue":"4","key":"30_CR19","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1137\/08074489X","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman, D.A., Teng, S.H.: Spectral sparsification of graphs. SIAM J. Comput. 40(4), 981\u20131025 (2011)","journal-title":"SIAM J. Comput."},{"key":"30_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54075-2","volume-title":"Upper and Lower Bounds for Stochastic Processes","author":"M Talagrand","year":"2014","unstructured":"Talagrand, M.: Upper and Lower Bounds for Stochastic Processes. Springer, Cham (2014)"},{"key":"30_CR21","doi-asserted-by":"publisher","unstructured":"Vishnoi, N.K.: $$Lx = b$$, laplacian solvers and their algorithmic applications. Found. Trends\u00ae Theor. Comput. Sci. 8(1-2), 1\u2013141 (2013). https:\/\/doi.org\/10.1561\/0400000054","DOI":"10.1561\/0400000054"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-59835-7_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T07:14:41Z","timestamp":1716275681000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-59835-7_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031598340","9783031598357"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-59835-7_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"22 May 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of the article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"The full version of the article can be found at .","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Full version"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Wroc\u0142aw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ipco2024.ii.uni.wroc.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}