{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:58Z","timestamp":1781077738541,"version":"3.54.1"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,4,12]],"date-time":"2024-04-12T00:00:00Z","timestamp":1712880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF 1565264 and CNS 1618026"],"award-info":[{"award-number":["CCF 1565264 and CNS 1618026"]}]},{"name":"Simons Investigator Award to Madhu Sudan"},{"name":"NSF","award":["CCF 1715187 and CCF 2152413"],"award-info":[{"award-number":["CCF 1715187 and CCF 2152413"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>\n            A constraint satisfaction problem (CSP),\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\textsf {Max-CSP}(\\mathcal {F})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , is specified by a finite set of constraints\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal {F}\\subseteq \\lbrace [q]^k \\rightarrow \\lbrace 0,1\\rbrace \\rbrace\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            for positive integers\n            <jats:italic>q<\/jats:italic>\n            and\n            <jats:italic>k<\/jats:italic>\n            . An instance of the problem on\n            <jats:italic>n<\/jats:italic>\n            variables is given by\n            <jats:italic>m<\/jats:italic>\n            applications of constraints from\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal {F}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            to subsequences of the\n            <jats:italic>n<\/jats:italic>\n            variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the (\u03b3 ,\u03b2)-approximation version of the problem for parameters 0 \u2264 \u03b2 \u2264 \u03b3 \u2264 1, the goal is to distinguish instances where at least \u03b3 fraction of the constraints can be satisfied from instances where at most \u03b2 fraction of the constraints can be satisfied.\n          <\/jats:p>\n          <jats:p>\n            In this work, we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal {F}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and every \u03b2 &lt; \u03b3, we show that either a linear sketching algorithm solves the problem in polylogarithmic space or the problem is not solvable by any sketching algorithm in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(o(\\sqrt {n})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems.\n          <\/jats:p>\n          <jats:p>\n            We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of\n            <jats:italic>q<\/jats:italic>\n            =\n            <jats:italic>k<\/jats:italic>\n            =2, where we get a dichotomy, and the case when the satisfying assignments of the constraints of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal {F}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            support a distribution on\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\([q]^k\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            with uniform marginals.\n          <\/jats:p>\n          <jats:p>\n            Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variables\n            <jats:italic>q<\/jats:italic>\n            = 2, binary constraints\n            <jats:italic>k<\/jats:italic>\n            =2, and singleton families\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(|\\mathcal {F}|=1\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and only considered the setting where constraints are placed on literals rather than variables.\n          <\/jats:p>\n          <jats:p>\n            Our positive results show wide applicability of bias-based algorithms used previously by [\n            <jats:xref ref-type=\"bibr\">47<\/jats:xref>\n            ] and [\n            <jats:xref ref-type=\"bibr\">41<\/jats:xref>\n            ], which we extend to include richer norm estimation algorithms, by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [\n            <jats:xref ref-type=\"bibr\">56<\/jats:xref>\n            ], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results. In particular, previous works used Fourier analysis over the Boolean cube to initiate their results and the results seemed particularly tailored to functions on Boolean literals (i.e., with negations). Our techniques surprisingly allow us to get to general\n            <jats:italic>q<\/jats:italic>\n            -ary CSPs without negations by appealing to the same Fourier analytic starting point over Boolean hypercubes.\n          <\/jats:p>","DOI":"10.1145\/3649435","type":"journal-article","created":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T12:28:15Z","timestamp":1709209695000},"page":"1-74","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Sketching Approximability of All Finite CSPs"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9089-2003","authenticated-orcid":false,"given":"Chi-Ning","family":"Chou","sequence":"first","affiliation":[{"name":"School of Engineering and Applied Sciences, Harvard University, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7847-1027","authenticated-orcid":false,"given":"Alexander","family":"Golovnev","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Georgetown University, Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3718-6489","authenticated-orcid":false,"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[{"name":"School of Engineering and Applied Sciences, Harvard University, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0294-5425","authenticated-orcid":false,"given":"Santhoshini","family":"Velusamy","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute, Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,4,12]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Yuqing Ai Wei Hu Yi Li and David P. Woodruff. 2016. New characterizations in turnstile streams with applications. In 31st Conference on Computational Complexity (CCC\u201916). LIPIcs 20:1\u201320:22."},{"key":"e_1_3_3_3_2","unstructured":"Alexandr Andoni. 2020. Personal Communication. (December24 2020)."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","unstructured":"Alexandr Andoni Robert Krauthgamer and Krzysztof Onak. 2011. Streaming algorithms via precision sampling. In IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS\u201911). IEEE 363\u2013372. DOI:10.1109\/FOCS.2011.82","DOI":"10.1109\/FOCS.2011.82"},{"key":"e_1_3_3_5_2","first-page":"708","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA\u201922)","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi. 2022. A two-pass (conditional) lower bound for semi-streaming maximum matching. In ACM-SIAM Symposium on Discrete Algorithms (SODA\u201922). SIAM, 708\u2013742."},{"key":"e_1_3_3_6_2","first-page":"19:1\u201319:13","volume-title":"48th International Colloquium on Automata, Languages, and Programming (ICALP\u201921)","author":"Assadi Sepehr","year":"2021","unstructured":"Sepehr Assadi and Soheil Behnezhad. 2021. Beating two-thirds for random-order streaming matching. In 48th International Colloquium on Automata, Languages, and Programming (ICALP\u201921). LIPIcs, 19:1\u201319:13."},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","unstructured":"Sepehr Assadi Soheil Behnezhad Sanjeev Khanna and Huan Li. 2023. On regularity lemma and barriers in streaming and dynamic matching. In 55th Annual ACM Symposium on Theory of Computing (STOC 2023). ACM 131\u2013144.","DOI":"10.1145\/3564246.3585110"},{"key":"e_1_3_3_8_2","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/3519935.3520016","volume-title":"54th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201922)","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi, Andrew Chen, and Glenn Sun. 2022. Deterministic graph coloring in the streaming model. In 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201922). ACM, 261\u2013274."},{"key":"e_1_3_3_9_2","first-page":"6:1\u20136:18","volume-title":"35th International Symposium on Distributed Computing (DISC\u201921)","author":"Assadi Sepehr","year":"2021","unstructured":"Sepehr Assadi and Aditi Dudeja. 2021. Ruling sets in random order and adversarial streams. In 35th International Symposium on Distributed Computing (DISC\u201921). LIPIcs, 6:1\u20136:18."},{"key":"e_1_3_3_10_2","first-page":"627","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA\u201922)","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. 2022. Semi-streaming bipartite matching in fewer passes and optimal space. In ACM-SIAM Symposium on Discrete Algorithms (SODA\u201922). SIAM, 627\u2013669."},{"key":"e_1_3_3_11_2","first-page":"1723","volume-title":"28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Assadi Sepehr","year":"2017","unstructured":"Sepehr Assadi, Sanjeev Khanna, and Yang Li. 2017. On estimating maximum matching size in graph streams. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). SIAM, 1723\u20131742."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1095482"},{"key":"e_1_3_3_13_2","first-page":"1345","volume-title":"27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916)","author":"Assadi Sepehr","year":"2016","unstructured":"Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. 2016. Maximum matchings in dynamic graph streams and the simultaneous communication model. In 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). SIAM, 1345\u20131364."},{"key":"e_1_3_3_14_2","first-page":"354","volume-title":"61st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201920)","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. In 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201920). IEEE, 354\u2013364."},{"key":"e_1_3_3_15_2","first-page":"1193","volume-title":"63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201922)","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi, Gillat Kol, and Zhijun Zhang. 2022. Rounds vs communication tradeoffs for maximal independent sets. In 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201922). IEEE, 1193\u20131204."},{"key":"e_1_3_3_16_2","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1145\/3519935.3520005","volume-title":"54th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201922)","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi, Pankaj Kumar, and Parth Mittal. 2022. Brooks\u2019 theorem in graph streams: A single-pass semi-streaming algorithm for coloring. In 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201922). ACM, 234\u2013247."},{"key":"e_1_3_3_17_2","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/3406325.3451110","volume-title":"53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201921)","author":"Assadi Sepehr","year":"2021","unstructured":"Sepehr Assadi and Vishvajeet N. 2021. Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma. In 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201921). ACM, 612\u2013625."},{"key":"e_1_3_3_18_2","first-page":"342","volume-title":"61st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201920)","author":"Assadi Sepehr","year":"2020","unstructured":"Sepehr Assadi and Ran Raz. 2020. Near-quadratic lower bounds for two-pass graph streaming algorithms. In 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201920). IEEE, 342\u2013353."},{"key":"e_1_3_3_19_2","first-page":"9:1\u20139:23","volume-title":"13th Innovations in Theoretical Computer Science Conference (ITCS\u201922)","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi and Vihan Shah. 2022. An asymptotically optimal algorithm for maximum matching in dynamic streams. In 13th Innovations in Theoretical Computer Science Conference (ITCS\u201922). LIPIcs, 9:1\u20139:23."},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1145\/3564246.3585192","volume-title":"55th Annual ACM Symposium on Theory of Computing (STOC\u201923)","author":"Assadi Sepehr","year":"2023","unstructured":"Sepehr Assadi and Janani Sundaresan. 2023. (Noisy) gap cycle counting strikes back: Random order streaming lower bounds for connected components and beyond. In 55th Annual ACM Symposium on Theory of Computing (STOC\u201923). ACM, 183\u2013195."},{"key":"e_1_3_3_21_2","first-page":"10:1\u201310:20","volume-title":"13th Innovations in Theoretical Computer Science Conference (ITCS\u201922)","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi and Chen Wang. 2022. Sublinear time and space algorithms for correlation clustering via sparse-dense decompositions. In 13th Innovations in Theoretical Computer Science Conference (ITCS\u201922). LIPIcs, 10:1\u201310:20."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0272-6"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","unstructured":"Libor Barto and Marcin Kozik. 2012. Robust satisfiability of constraint satisfaction problems. In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC\u201912). ACM 931\u2013940. DOI:10.1145\/2213977.2214061","DOI":"10.1145\/2213977.2214061"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33099-2"},{"key":"e_1_3_3_25_2","first-page":"129","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA\u201923)","author":"Behnezhad Soheil","year":"2023","unstructured":"Soheil Behnezhad. 2023. Dynamic algorithms for maximum matching size. In ACM-SIAM Symposium on Discrete Algorithms (SODA\u201923). SIAM, 129\u2013162."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_3_3_27_2","first-page":"38:1\u201338:23","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\u201922)","author":"Boyland Joanna","year":"2022","unstructured":"Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, and Santhoshini Velusamy. 2022. On sketching approximations for symmetric Boolean CSPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\u201922). LIPIcs, 38:1\u201338:23."},{"key":"e_1_3_3_28_2","first-page":"319","volume-title":"58th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201917)","author":"Bulatov Andrei A.","year":"2017","unstructured":"Andrei A. Bulatov. 2017. A dichotomy theorem for nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201917). IEEE, 319\u2013330."},{"key":"e_1_3_3_29_2","first-page":"94","article-title":"Data stream algorithms","author":"Chakrabarti Amit","year":"2020","unstructured":"Amit Chakrabarti. 2020. Data stream algorithms. Lecture Notes on Data Stream Algorithms (2020), 94. https:\/\/www.cs.dartmouth.edu\/ac\/Teach\/data-streams-lecnotes.pdf","journal-title":"Lecture Notes on Data Stream Algorithms"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/120861072"},{"key":"e_1_3_3_31_2","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1145\/3406325.3451038","volume-title":"53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201921)","author":"Chen Lijie","year":"2021","unstructured":"Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. 2021. Almost optimal super-constant-pass streaming lower bounds for reachability. In 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201921). ACM, 570\u2013583."},{"key":"e_1_3_3_32_2","first-page":"52:1\u201352:19","volume-title":"48th International Colloquium on Automata, Languages, and Programming (ICALP\u201921)","author":"Chen Lijie","year":"2021","unstructured":"Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. 2021. Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP\u201921). LIPIcs, 52:1\u201352:19."},{"key":"e_1_3_3_33_2","first-page":"878","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA\u201923)","author":"Chen Lijie","year":"2023","unstructured":"Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. 2023. Towards multi-pass streaming lower bounds for optimal approximation of max-cut. In ACM-SIAM Symposium on Discrete Algorithms (SODA\u201923). SIAM, 878\u2013924."},{"key":"e_1_3_3_34_2","first-page":"37:1\u201337:16","volume-title":"50th International Colloquium on Automata, Languages, and Programming (ICALP\u201923)","author":"Chen Yu","year":"2023","unstructured":"Yu Chen, Sanjeev Khanna, and Zihan Tan. 2023. Sublinear algorithms and lower bounds for estimating MST and TSP cost in general metrics. In 50th International Colloquium on Automata, Languages, and Programming (ICALP\u201923). LIPIcs, 37:1\u201337:16."},{"key":"e_1_3_3_35_2","first-page":"486","volume-title":"63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201922)","author":"Chiplunkar Ashish","year":"2022","unstructured":"Ashish Chiplunkar, John Kallaugher, Michael Kapralov, and Eric Price. 2022. Factorial lower bounds for (almost) random order streams. In 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201922). IEEE, 486\u2013497."},{"key":"e_1_3_3_36_2","first-page":"1197","volume-title":"62nd IEEE Annual Symposium on Foundations of Computer Science","author":"Chou Chi-Ning","year":"2022","unstructured":"Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. 2022. Approximability of all finite CSPs with linear sketches. In 62nd IEEE Annual Symposium on Foundations of Computer Science. IEEE, 1197\u20131208."},{"key":"e_1_3_3_37_2","first-page":"1","article-title":"Classification of the streaming approximability of Boolean CSPs","volume":"2102","author":"Chou Chi-Ning","year":"2021","unstructured":"Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. 2021. Classification of the streaming approximability of Boolean CSPs. CoRR abs\/2102.12351v1 (February 24, 2021), 1\u201349. arxiv:2102.12351https:\/\/arxiv.org\/abs\/2102.12351v1","journal-title":"CoRR"},{"key":"e_1_3_3_38_2","first-page":"1","article-title":"Approximability of all Boolean CSPs with linear sketches","volume":"2102","author":"Chou Chi-Ning","year":"2021","unstructured":"Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. 2021. Approximability of all Boolean CSPs with linear sketches. CoRR abs\/2102.12351v3 (April 14, 2021), 1\u201360. arxiv:2102.12351https:\/\/arxiv.org\/abs\/2102.12351v3","journal-title":"CoRR"},{"key":"e_1_3_3_39_2","first-page":"1","article-title":"Approximability of all finite CSPs with linear sketches","volume":"2105","author":"Chou Chi-Ning","year":"2021","unstructured":"Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. 2021. Approximability of all finite CSPs with linear sketches. CoRR abs\/2105.01161 (May3, 2021), 1\u201375. arxiv:2105.01161https:\/\/arxiv.org\/abs\/2105.01161","journal-title":"CoRR"},{"key":"e_1_3_3_40_2","first-page":"35:1\u201335:17","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\u201922)","author":"Chou Chi-Ning","year":"2022","unstructured":"Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, and Santhoshini Velusamy. 2022. Sketching approximability of (weak) monarchy predicates. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\u201922). LIPIcs, 35:1\u201335:17."},{"key":"e_1_3_3_41_2","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1145\/3519935.3519983","volume-title":"54th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201922)","author":"Chou Chi-Ning","year":"2022","unstructured":"Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy. 2022. Linear space streaming lower bounds for approximating CSPs. In 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201922). ACM, 275\u2013288."},{"key":"e_1_3_3_42_2","first-page":"330","volume-title":"61st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201920)","author":"Chou Chi-Ning","year":"2020","unstructured":"Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy. 2020. Optimal streaming approximations for all Boolean Max-2CSPs and Max-kSAT. In 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201920). IEEE, 330\u2013341."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2540090"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/070706550"},{"key":"e_1_3_3_45_2","first-page":"468","volume-title":"23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912)","author":"Goel Ashish","year":"2012","unstructured":"Ashish Goel, Michael Kapralov, and Sanjeev Khanna. 2012. On the communication and streaming complexity of maximum bipartite matching. In 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912). SIAM, 468\u2013485."},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/090756144"},{"key":"e_1_3_3_47_2","first-page":"5:1\u20135:12","volume-title":"APPROX 2019","author":"Guruswami Venkatesan","year":"2019","unstructured":"Venkatesan Guruswami and Runzhou Tao. 2019. Streaming hardness of unique games. In APPROX 2019. LIPIcs, 5:1\u20135:12."},{"key":"e_1_3_3_48_2","first-page":"8:1\u20138:19","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\u201917)","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\u201917). LIPIcs, 8:1\u20138:19."},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_3_50_2","first-page":"460","volume-title":"32nd International Symposium on Theoretical Aspects of Computer Science (STACS\u201915)","author":"Huang Zengfeng","year":"2015","unstructured":"Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic, and Qin Zhang. 2015. Communication complexity of approximate matching in distributed graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS\u201915). LIPIcs, 460\u2013473."},{"key":"e_1_3_3_51_2","first-page":"68","volume-title":"29th Annual Symposium on Foundations of Computer Science (FOCS\u201988)","author":"Kahn Jeff","year":"1988","unstructured":"Jeff Kahn, Gil Kalai, and Nathan Linial. 1988. The influence of variables on Boolean functions. In 29th Annual Symposium on Foundations of Computer Science (FOCS\u201988). IEEE, 68\u201380."},{"key":"e_1_3_3_52_2","doi-asserted-by":"crossref","first-page":"1223","DOI":"10.1145\/3357713.3384278","volume-title":"52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201920)","author":"Kallaugher John","year":"2020","unstructured":"John Kallaugher and Eric Price. 2020. Separations and equivalences between turnstile streaming and linear sketching. In 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201920). ACM, 1223\u20131236."},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"e_1_3_3_54_2","first-page":"1679","volume-title":"SODA 2013","author":"Kapralov Michael","year":"2013","unstructured":"Michael Kapralov. 2013. Better bounds for matchings in the streaming model. In SODA 2013. SIAM, 1679\u20131697."},{"key":"e_1_3_3_55_2","first-page":"1874","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921)","author":"Kapralov Michael","year":"2021","unstructured":"Michael Kapralov. 2021. Space lower bounds for approximating maximum matching in the edge arrival model. In ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921). SIAM, 1874\u20131893."},{"key":"e_1_3_3_56_2","first-page":"734","volume-title":"25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914)","author":"Kapralov Michael","year":"2014","unstructured":"Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. 2014. Approximating matching size from random streams. In 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914). SIAM, 734\u2013751."},{"key":"e_1_3_3_57_2","first-page":"1263","volume-title":"26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Kapralov Michael","year":"2015","unstructured":"Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. 2015. Streaming lower bounds for approximating MAX-CUT. In 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915). SIAM, 1263\u20131282."},{"key":"e_1_3_3_58_2","first-page":"1703","volume-title":"28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Kapralov Michael","year":"2017","unstructured":"Michael Kapralov, Sanjeev Khanna, Madhu Sudan, and Ameya Velingker. 2017. \\((1+ \\Omega (1))\\) -approximation to MAX-CUT requires linear space. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). SIAM, 1703\u20131722."},{"key":"e_1_3_3_59_2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/3313276.3316364","volume-title":"51st Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201919)","author":"Kapralov Michael","year":"2019","unstructured":"Michael Kapralov and Dmitry Krachun. 2019. An optimal space lower bound for approximating MAX-CUT. In 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201919). ACM, 277\u2013288."},{"key":"e_1_3_3_60_2","first-page":"767","volume-title":"34th Annual ACM Symposium on Theory of Computing (STOC\u201902)","author":"Khot Subhash","year":"2002","unstructured":"Subhash Khot. 2002. On the power of unique 2-prover 1-round games. In 34th Annual ACM Symposium on Theory of Computing (STOC\u201902). ACM, 767\u2013775."},{"key":"e_1_3_3_61_2","first-page":"634","volume-title":"Symposium on Theory of Computing (STOC\u201914)","author":"Khot Subhash","year":"2014","unstructured":"Subhash Khot, Madhur Tulsiani, and Pratik Worah. 2014. A characterization of strong approximation resistance. In Symposium on Theory of Computing (STOC\u201914). ACM, 634\u2013643."},{"key":"e_1_3_3_62_2","first-page":"80:1\u201380:15","volume-title":"14th Innovations in Theoretical Computer Science Conference (ITCS\u201923)","author":"Kol Gillat","year":"2023","unstructured":"Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, and Huacheng Yu. 2023. Characterizing the multi-pass streaming complexity for solving Boolean CSPs exactly. In 14th Innovations in Theoretical Computer Science Conference (ITCS\u201923). LIPIcs, 80:1\u201380:15."},{"key":"e_1_3_3_63_2","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1007\/978-3-662-48350-3_70","volume-title":"Algorithms - ESA 2015-23rd Annual European Symposium (ESA\u201915)","author":"Konrad Christian","year":"2015","unstructured":"Christian Konrad. 2015. Maximum matching in turnstile streams. In Algorithms - ESA 2015-23rd Annual European Symposium (ESA\u201915). Springer, 840\u2013852."},{"key":"e_1_3_3_64_2","first-page":"484","volume-title":"Innovations in Theoretical Computer Science 2012 (ITCS\u201912)","author":"Kun G\u00e1bor","year":"2012","unstructured":"G\u00e1bor Kun, Ryan O\u2019Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou. 2012. Linear programming, width-1 CSPs, and robust satisfaction. In Innovations in Theoretical Computer Science 2012 (ITCS\u201912). ACM, 484\u2013495."},{"key":"e_1_3_3_65_2","first-page":"174","volume-title":"Symposium on Theory of Computing (STOC\u201914)","author":"Li Yi","year":"2014","unstructured":"Yi Li, Huy L. Nguyen, and David P. Woodruff. 2014. Turnstile streaming algorithms might as well be linear sketches. In Symposium on Theory of Computing (STOC\u201914). ACM, 174\u2013183."},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"e_1_3_3_67_2","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1145\/3313276.3316374","volume-title":"51st Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201919)","author":"Potechin Aaron","year":"2019","unstructured":"Aaron Potechin. 2019. On the approximation resistance of balanced linear threshold functions. In 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201919). ACM, 430\u2013441."},{"key":"e_1_3_3_68_2","first-page":"245","volume-title":"40th Annual ACM Symposium on Theory of Computing (STOC\u201908)","author":"Raghavendra Prasad","year":"2008","unstructured":"Prasad Raghavendra. 2008. Optimal algorithms and inapproximability results for every CSP? In 40th Annual ACM Symposium on Theory of Computing (STOC\u201908). ACM, 245\u2013254."},{"key":"e_1_3_3_69_2","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BFb0032036","volume-title":"Automata, Languages and Programming, 17th International Colloquium (ICALP\u201990)","author":"Razborov Alexander A.","year":"1990","unstructured":"Alexander A. Razborov. 1990. On the distributional complexity of disjointness. In Automata, Languages and Programming, 17th International Colloquium (ICALP\u201990). Springer, 249\u2013253."},{"key":"e_1_3_3_70_2","first-page":"4083","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA\u201923)","author":"Saxena Raghuvansh R.","year":"2023","unstructured":"Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, and Santhoshini Velusamy. 2023. Streaming complexity of CSPs with randomly ordered constraints. In ACM-SIAM Symposium on Discrete Algorithms (SODA\u201923). SIAM, 4083\u20134103."},{"key":"e_1_3_3_71_2","volume-title":"64th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201923)","author":"Saxena Raghuvansh R.","year":"2023","unstructured":"Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, and Santhoshini Velusamy. 2023. Improved streaming algorithms for maximum directed cut via smoothed snapshots. In 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201923). IEEE."},{"key":"e_1_3_3_72_2","first-page":"216","volume-title":"10th Annual ACM Symposium on Theory of Computing (STOC\u201978)","author":"Schaefer Thomas J.","year":"1978","unstructured":"Thomas J. Schaefer. 1978. The complexity of satisfiability problems. In 10th Annual ACM Symposium on Theory of Computing (STOC\u201978). ACM, 216\u2013226."},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a008"},{"key":"e_1_3_3_74_2","first-page":"17:1\u201317:19","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\u201921)","author":"Singer Noah","year":"2021","unstructured":"Noah Singer, Madhu Sudan, and Santhoshini Velusamy. 2021. Streaming approximation resistance of every ordering CSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\u201921). LIPIcs, 17:1\u201317:19."},{"key":"e_1_3_3_75_2","unstructured":"Noah G. Singer. 2023. Oblivious algorithms for the Max-kAND problem. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\u201923)."},{"key":"e_1_3_3_76_2","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.2012.001"},{"key":"e_1_3_3_77_2","first-page":"331","volume-title":"58th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201917)","author":"Zhuk Dmitriy","year":"2017","unstructured":"Dmitriy Zhuk. 2017. A proof of CSP dichotomy conjecture. In 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201917). IEEE, 331\u2013342."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649435","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3649435","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:21Z","timestamp":1750291401000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3649435"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,12]]},"references-count":76,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3649435"],"URL":"https:\/\/doi.org\/10.1145\/3649435","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,12]]},"assertion":[{"value":"2022-03-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}