{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:33Z","timestamp":1781028273558,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":29,"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.3800915","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"2118-2129","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Half-Approximating Maximum Dicut in the Streaming Setting"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-6451-3985","authenticated-orcid":false,"given":"Amir","family":"Azarmehr","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0104-633X","authenticated-orcid":false,"given":"Soheil","family":"Behnezhad","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1044-0117","authenticated-orcid":false,"given":"Shane","family":"Ferrante","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8744-7427","authenticated-orcid":false,"given":"Mohammad","family":"Saneian","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"MAX-CUT, Matching Size, and Other Problems. CoRR, abs\/2009.03038","author":"Assadi Sepehr","year":"2020","unstructured":"Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, and Huacheng Yu. 2020. Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. CoRR, abs\/2009.03038 (2020), arXiv:2009.03038."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Sepehr Assadi and Vishvajeet N. 2021. Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma. CoRR abs\/2104.04908 (2021) arXiv:2104.04908.","DOI":"10.1145\/3406325.3451110"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.16"},{"key":"e_1_3_2_1_4_1","volume-title":"Closed-form expressions for the sketching approximability of (some) symmetric Boolean CSPs. CoRR, abs\/2112.06319","author":"Boyland Joanna","year":"2021","unstructured":"Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, and Santhoshini Velusamy. 2021. Closed-form expressions for the sketching approximability of (some) symmetric Boolean CSPs. CoRR, abs\/2112.06319 (2021), arXiv:2112.06319."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-72751-6_4"},{"key":"e_1_3_2_1_7_1","volume-title":"Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. CoRR, abs\/2102.11251","author":"Chen Lijie","year":"2021","unstructured":"Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, and Huacheng Yu. 2021. Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. CoRR, abs\/2102.11251 (2021), arXiv:2102.11251."},{"key":"e_1_3_2_1_8_1","volume-title":"Linear Space Streaming Lower Bounds for Approximating CSPs. CoRR, abs\/2106.13078","author":"Chou Chi-Ning","year":"2021","unstructured":"Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy. 2021. Linear Space Streaming Lower Bounds for Approximating CSPs. CoRR, abs\/2106.13078 (2021), arXiv:2106.13078."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00039"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2022.35"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-013-9806-Z"},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1723\u20131742","author":"Gopalan Parikshit","unstructured":"Parikshit Gopalan, Kishore Kothapalli, and S. Venkatasubramanian. 2017. Streaming Graph Partitioning Algorithms for Directed Cuts. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1723\u20131742."},{"key":"e_1_3_2_1_13_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM","author":"Guruswami Venkatesan","year":"2017","unstructured":"Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy. 2017. Streaming complexity of approximating max 2csp and max acyclic subgraph. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2017). 8\u20131."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1952.10483446"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"John Kallaugher and Ojas Parekh. 2022. The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut. arxiv:2206.00213.","DOI":"10.2172\/2432219"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"John Kallaugher Ojas Parekh and Nadezhda Voronova. 2023. Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. arxiv:2311.14123.","DOI":"10.1145\/3618260.3649709"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.84"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.112"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316364"},{"key":"e_1_3_2_1_20_1","unstructured":"Dmitry Kogan and Robert Krauthgamer. 2014. Sketching Cuts in Graphs and Hypergraphs. arxiv:1409.2391."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2023.80"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.CH156"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00055"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.111"},{"key":"e_1_3_2_1_25_1","volume-title":"Streaming approximation resistance of every ordering CSP. CoRR, abs\/2105.01782","author":"Singer Noah","year":"2021","unstructured":"Noah Singer, Madhu Sudan, and Santhoshini Velusamy. 2021. Streaming approximation resistance of every ordering CSP. CoRR, abs\/2105.01782 (2021), arXiv:2105.01782."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2023.15"},{"key":"e_1_3_2_1_27_1","volume-title":"TR22-065","author":"Sudan Madhu","year":"2022","unstructured":"Madhu Sudan. 2022. Streaming and Sketching Complexity of CSPs: A survey. Electron. Colloquium Comput. Complex., TR22-065 (2022), ECCC:TR22-065."},{"key":"e_1_3_2_1_28_1","unstructured":"Santhoshini Velusamy. 2025. Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes. arXiv preprint arXiv:2512.19521."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"}],"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.3800915","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:55:44Z","timestamp":1781027744000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800915"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":29,"alternative-id":["10.1145\/3798129.3800915","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800915","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"}}]}}