{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:41Z","timestamp":1778807861819,"version":"3.51.4"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF Award","award":["CCF (AF) 2307106"],"award-info":[{"award-number":["CCF (AF) 2307106"]}]},{"name":"National Institute of Health","award":["5R01 HG 10798-2"],"award-info":[{"award-number":["5R01 HG 10798-2"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>In this paper, we consider two fundamental cut approximation problems on large graphs. We prove new lower bounds for both problems that are optimal up to logarithmic factors.<\/jats:p>\n          <jats:p>\n            The first problem is approximating cuts in balanced directed graphs. In this problem, we want to build a data structure that can provide (1 \u00b1 \u03b5)-approximation of cut values on a graph with n vertices. For arbitrary directed graphs, such a data structure requires \u03a9(n\n            <jats:sup>2<\/jats:sup>\n            ) bits even for constant \u03b5. To circumvent this, recent works study \u03b2-balanced graphs, meaning that for every directed cut, the total weight of edges in one direction is at most \u03b2 times the total weight in the other direction. We consider the for-each model, where the goal is to approximate each cut with constant probability, and the for-all model, where all cuts must be preserved simultaneously. We improve the previous \u00d8mega(n \u221a\u03b2\/\u03b5) lower bound in the for-each model to ~\u03a9 (n \u221a\u03b2 \/\u03b5) and we improve the previous \u03a9(n \u03b2\/\u03b5) lower bound in the for-all model to \u03a9(n \u03b2\/\u03b5\n            <jats:sup>2<\/jats:sup>\n            ). This resolves the main open questions of (Cen et al., ICALP, 2021).\n          <\/jats:p>\n          <jats:p>\n            The second problem is approximating the global minimum cut in a local query model, where we can only access the graph via degree, edge, and adjacency queries. We prove an \u03a9L(min m, m\/\u03b5\n            <jats:sup>2<\/jats:sup>\n            k R) lower bound for this problem, which improves the previous \u03a9L(m\/k R) lower bound, where m is the number of edges, k is the minimum cut size, and we seek a (1+\u03b5)-approximation. In addition, we show that existing upper bounds with minor modifications match our lower bound up to logarithmic factors.\n          <\/jats:p>","DOI":"10.1145\/3651148","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-18","source":"Crossref","is-referenced-by-count":1,"title":["Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0019-2570","authenticated-orcid":false,"given":"Yu","family":"Cheng","sequence":"first","affiliation":[{"name":"Brown University, Providence, RI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-0659-7739","authenticated-orcid":false,"given":"Max","family":"Li","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-5162-3328","authenticated-orcid":false,"given":"Honghao","family":"Lin","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-9399-8605","authenticated-orcid":false,"given":"Zi-Yi","family":"Tai","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2158-1380","authenticated-orcid":false,"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7441-2583","authenticated-orcid":false,"given":"Jason","family":"Zhang","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840753"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772873"},{"key":"e_1_2_1_4_1","first-page":"47","volume-title":"Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC)","author":"Bencz\u00far A. A.","year":"1996","unstructured":"Bencz\u00far, A. A., and Karger, D. R. Approximating s-t minimum cuts in \u00d5(n2) time. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC) (1996), ACM, pp. 47--55."},{"key":"e_1_2_1_5_1","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM)","author":"Bishnu A.","year":"2021","unstructured":"Bishnu, A., Ghosh, A., Mishra, G., and Paraashar, M. Query complexity of global minimum cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM) (2021), vol. 207 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 6:1--6:15."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.158"},{"key":"e_1_2_1_7_1","series-title":"LIPIcs","first-page":"1","volume-title":"48th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Cen R.","year":"2021","unstructured":"Cen, R., Cheng, Y., Panigrahi, D., and Sun, K. Sparsification of directed graphs via cut balance. In 48th International Colloquium on Automata, Languages, and Programming (ICALP) (2021), vol. 198 of LIPIcs, pp. 45:1--45:21."},{"key":"e_1_2_1_8_1","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM)","author":"Eden T.","year":"2018","unstructured":"Eden, T., and Rosenbaum, W. Lower bounds for approximating graph parameters via communication complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM) (2018), vol. 116 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 11:1--11:18."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897654"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1091666"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04693-4_17"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090267"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370100003"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055477"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_2_1_16_1","first-page":"1","volume-title":"9th Innovations in Theoretical Computer Science Conference (ITCS)","volume":"94","author":"Rubinstein A.","year":"2018","unstructured":"Rubinstein, A., Schramm, T., and Weinberg, S. M. Computing exact minimum cuts without knowing the graph. In 9th Innovations in Theoretical Computer Science Conference (ITCS) (2018), vol. 94 of LIPIcs, pp. 39:1--39:16."},{"key":"e_1_2_1_17_1","first-page":"6","article-title":"Graph sparsification by effective resistances","volume":"40","author":"Spielman D. A.","year":"2011","unstructured":"Spielman, D. A., and Srivastava, N. Graph sparsification by effective resistances. SIAM J. Comput. 40, 6 (2011), 1913--1926.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.54"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651148","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651148","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:38Z","timestamp":1755898778000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651148"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651148"],"URL":"https:\/\/doi.org\/10.1145\/3651148","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}