{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T23:23:17Z","timestamp":1765927397699,"version":"3.48.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2025,12,15]]},"abstract":"<jats:p>Request for Columns! I invite any reader who has knowledge of some area to contact me and arrange to write a column about open problems in that area. That area can be (1) broad or narrow or anywhere inbetween, and (2) really important or really unimportant or anywhere inbetween.<\/jats:p>","DOI":"10.1145\/3785512.3785516","type":"journal-article","created":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T21:34:47Z","timestamp":1765834487000},"page":"25-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Nine lower bound conjectures on streaming approximation algorithms for CSPs"],"prefix":"10.1145","volume":"56","author":[{"given":"Noah G.","family":"Singer","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,12,15]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/3406325.3451110"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1109\/FOCS46700.2020.00041"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.4230\/LIPICS.ICALP.2018.16"},{"doi-asserted-by":"publisher","unstructured":"Joanna Boyland Michael Hwang Tarun Prasad Noah Singer and Santhoshini Velusamy. On sketching approximations for symmetric Boolean CSPs. In Amit Chakrabarti and Chaitanya Swamy editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX 2022) volume 245 of LIPIcs pages 38:1--38:23 virtual July 2022. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik. doi: 10.4230\/LIPIcs.APPROX\/RANDOM.2022.38.","key":"e_1_2_1_4_1","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2022.38"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1109\/FOCS57990.2023.00023"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1137\/1.9781611977554.ch35"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1109\/FOCS46700.2020.00039"},{"key":"e_1_2_1_8_1","volume-title":"Approximability of all Boolean CSPs with linear sketches","author":"Chou Chi-Ning","year":"2021","unstructured":"Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. Approximability of all Boolean CSPs with linear sketches. February 2021. URL https:\/\/arxiv.org\/abs\/2102.12351."},{"doi-asserted-by":"publisher","unstructured":"Chi-Ning Chou Alexander Golovnev Amirbehshad Shahrasbi Madhu Sudan and Santhoshini Velusamy. Sketching Approximability of (Weak) Monarchy Predicates. In Amit Chakrabarti and Chaitanya Swamy editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX 2022) volume 245 of LIPIcs pages 35:1--35:17 virtual 2022. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik. doi: 10.4230\/LIPIcs.APPROX\/RANDOM.2022.35.","key":"e_1_2_1_9_1","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2022.35"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/3519935.3519983"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/3649435"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1006\/jcss"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_14_1","volume-title":"Shuo Wang. Multi-Pass Streaming Lower Bounds for Approximating Max-Cut. In Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025","author":"Fei Yumou","year":"2025","unstructured":"Yumou Fei, Dor Minzer, and Shuo Wang. Multi-Pass Streaming Lower Bounds for Approximating Max-Cut. In Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025), Sydney, Australia, March 2025. IEEE Computer Society."},{"key":"e_1_2_1_15_1","volume-title":"September","author":"Fei Yumou","year":"2025","unstructured":"Yumou Fei, Dor Minzer, and Shuo Wang. A Dichotomy Theorem for Multi-Pass Streaming CSPs, September 2025."},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1007\/s00453-013--9806-z"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/227683.227684"},{"doi-asserted-by":"publisher","unstructured":"Venkatesan Guruswami and Runzhou Tao. Streaming Hardness of Unique Games. In Dimitris Achlioptas and L\u00b4aszl\u00b4o A. V\u00b4egh editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX 2019) volume 145 of LIPIcs pages 5:1--5:12 Cambridge MA USA September 2019. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik. doi: 10.4230\/LIPIcs.APPROXRANDOM. 2019.5.","key":"e_1_2_1_18_1","DOI":"10.4230\/LIPIcs.APPROXRANDOM"},{"doi-asserted-by":"publisher","unstructured":"Venkatesan Guruswami Ameya Velingker and Santhoshini Velusamy. Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. In Klaus Jansen Jos\u00b4e D. P. Rolim David Williamson and Santosh S. Vempala editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX 2017) volume 81 of LIPIcs pages 8:1--8:19 Berkeley CA USA August 2017. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik. doi: 10.4230\/LIPIcs.APPROXRANDOM. 2017.8.","key":"e_1_2_1_19_1","DOI":"10.4230\/LIPIcs.APPROXRANDOM"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_21_1","volume-title":"May","author":"Hwang Samuel","year":"2024","unstructured":"Samuel Hwang, Noah G. Singer, and Santhoshini Velusamy. Oblivious algorithms for Maximum Directed Cut: New upper and lower bounds. Technical report, May 2024. URL https:\/\/arxiv.org\/abs\/2411. 12976."},{"key":"e_1_2_1_22_1","volume-title":"June","author":"Indyk Piotr","year":"2011","unstructured":"Piotr Indyk, Andrew McGregor, Ilan Newman, and Krzysztof Onak. Open problems in data streams, property testing, and related topics, June 2011. URL https:\/\/sublinear.info\/files\/ bertinoro2011_kanpur2009.pdf."},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1016\/0020-0190(87)90028-7"},{"key":"e_1_2_1_24_1","first-page":"498","volume-title":"Kallaugher and Ojas Parekh. The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022","author":"John","year":"2022","unstructured":"John Kallaugher and Ojas Parekh. The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), pages 498--506, Denver, CO, USA, October 2022. IEEE Computer Society. doi: 10.1109\/ FOCS54457.2022.00054."},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/3618260.3649709"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1137\/1.9781611978315.2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1145\/3313276.3316364"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1137\/1.9781611973730.84"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.5555\/3039686.3039798"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/509907.510017"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1137\/S0097539705447372"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/2688073.2688093"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.4230\/LIPIcs.ITCS.2023.80"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1145\/1374376.1374414"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1137\/1.9781611978322.111"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1109\/FOCS57990.2023.00055"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1137\/1.9781611977554.ch156"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_39_1","volume-title":"On Streaming Approximation Algorithms for Constraint Satisfaction Problems. Undergraduate thesis","author":"Singer Noah","year":"2022","unstructured":"Noah Singer. On Streaming Approximation Algorithms for Constraint Satisfaction Problems. Undergraduate thesis, Harvard University, Cambridge, MA, March 2022. URL https:\/\/nrs.harvard.edu\/URN- 3:HUL.INSTREPOS:37371750."},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1007\/s00037-024-00252--5"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.4230\/LIPIcs.APPROX\/"},{"key":"e_1_2_1_42_1","volume-title":"September","author":"Singer Noah G.","year":"2025","unstructured":"Noah G. Singer, Madhur Tulsiani, and Santhoshini Velusamy. Sketching approximations and LP approximations for finite CSPs are related, September 2025."},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.4230\/LIPIcs.ICALP.2022.5"},{"doi-asserted-by":"publisher","unstructured":"Xiaoming Sun and David P. Woodruff. Tight Bounds for Graph Problems in Insertion Streams. In Naveen Garg Klaus Jansen Anup Rao and Jos\u00b4e D. P. Rolim editors Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2015) volume 40 of LIPIcs pages 435--448 Princeton NJ USA 2015. Schloss Dagstuhl -- Leibniz-Zentrum f\u00a8ur Informatik. doi: 10.4230\/LIPIcs.APPROX-RANDOM.2015.435.","key":"e_1_2_1_44_1","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2015.435"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1137\/S0097539797328847"},{"unstructured":"Santhoshini Velusamy. Approximability of Constraint Satisfaction Problems in the Streaming Setting. PhD thesis Harvard University Cambridge MA May 2023. URL https:\/\/nrs.harvard.edu\/URN-3: HUL.INSTREPOS:37377430.","key":"e_1_2_1_46_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.1016\/j.ipl.2010.10.017"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3785512.3785516","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T23:18:41Z","timestamp":1765927121000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3785512.3785516"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,15]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,15]]}},"alternative-id":["10.1145\/3785512.3785516"],"URL":"https:\/\/doi.org\/10.1145\/3785512.3785516","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2025,12,15]]},"assertion":[{"value":"2025-12-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}