{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:34Z","timestamp":1781031454902,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800846","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1365-1375","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds on Flow Sparsifiers with Steiner Nodes"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-3595-1297","authenticated-orcid":false,"given":"Yu","family":"Chen","sequence":"first","affiliation":[{"name":"National University of Singapore, Department of Computer Science, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4844-8480","authenticated-orcid":false,"given":"Zihan","family":"Tan","sequence":"additional","affiliation":[{"name":"University of Minnesota, Department of Computer Science & Engineering, Minneapolis, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-8971-2064","authenticated-orcid":false,"given":"Mingyang","family":"Yang","sequence":"additional","affiliation":[{"name":"National University of Singapore, Department of Computer Science, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.44"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634094"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701395978"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.74"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.32"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00109"},{"key":"e_1_3_2_1_7_1","unstructured":"Yu Chen and Zihan Tan. 2024. Cut-preserving vertex sparsifiers for planar and quasi-bipartite graphs. arXiv preprint arXiv:2407.10852."},{"key":"e_1_3_2_1_8_1","volume-title":"51st International Colloquium on Automata, Languages, and Programming (ICALP","author":"Chen Yu","year":"2024","unstructured":"Yu Chen and Zihan Tan. 2024. Lower Bounds on 0-Extension with Steiner Nodes. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). 47\u20131."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.63"},{"key":"e_1_3_2_1_10_1","volume-title":"52nd International Colloquium on Automata, Languages, and Programming (ICALP","author":"Chen Yu","year":"2025","unstructured":"Yu Chen and Zihan Tan. 2025. Cut-Preserving Vertex Sparsifiers for Planar and Quasi-Bipartite Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). 53\u20131."},{"key":"e_1_3_2_1_11_1","unstructured":"Yu Chen Zihan Tan and Mingyang Yang. 2026. Lower Bounds on Flow Sparsifiers with Steiner Nodes. arXiv preprint arXiv:2602.12645."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214039"},{"key":"e_1_3_2_1_13_1","volume-title":"Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS","author":"Das Syamantak","year":"2024","unstructured":"Syamantak Das, Nikhil Kumar, and Daniel Vaz. 2024. Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). 45\u20131."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316379"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/130908440"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1163153"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-51741-4_9"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.132"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1592"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00119"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0504-8"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.02.011"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch91"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1151225"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.128"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806698"},{"key":"e_1_3_2_1_28_1","volume-title":"Vertex Sparsification for Edge Connectivity in Polynomial Time. In 14th Innovations in Theoretical Computer Science Conference (ITCS","author":"Liu Yang P","year":"2023","unstructured":"Yang P Liu. 2023. Vertex Sparsification for Edge Connectivity in Polynomial Time. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). 251, 83."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.31"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-016-1315-8"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.28"},{"key":"e_1_3_2_1_32_1","volume-title":"Expansion of random graphs: New proofs, new results. Inventiones mathematicae, 201, 3","author":"Puder Doron","year":"2015","unstructured":"Doron Puder. 2015. Expansion of random graphs: New proofs, new results. Inventiones mathematicae, 201, 3 (2015), 845\u2013908."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.162"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800846","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:03:55Z","timestamp":1781028235000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800846"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":33,"alternative-id":["10.1145\/3798129.3800846","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800846","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}