{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T12:23:50Z","timestamp":1752668630247,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council erc (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme","award":["803421"],"award-info":[{"award-number":["803421"]}]},{"DOI":"10.13039\/501100001870","name":"Foundation for Polish Science","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>\n            In the Boolean maximum constraint satisfaction problem\u2014\n            <jats:sc>Max CSP\u0393<\/jats:sc>\n            \u2014one is given a collection of weighted applications of constraints from a finite constraint language \u0393, over a common set of variables, and the goal is to assign Boolean values to the variables so that the total weight of satisfied constraints is maximized. There exists a concise dichotomy theorem providing a criterion on \u0393 for the problem to be polynomial-time solvable and stating that otherwise, it becomes NP-hard. We study the NP-hard cases through the lens of kernelization and provide a complete characterization of\n            <jats:sc>Max CSP\u0393<\/jats:sc>\n            with respect to the optimal compression size. Namely, we prove that\n            <jats:sc>Max CSP\u0393<\/jats:sc>\n            parameterized by the number of variables\n            <jats:italic>n<\/jats:italic>\n            is either polynomial-time solvable, or there exists an integer\n            <jats:italic>d<\/jats:italic>\n            \u2265 2 depending on \u0393, such that:\n            <jats:list list-type=\"ordered\">\n              <jats:list-item>\n                <jats:label>(1)<\/jats:label>\n                <jats:p>\n                  An instance of\n                  <jats:sc>Max CSP\u0393<\/jats:sc>\n                  can be compressed into an equivalent instance with \ud835\udcaa(\n                  <jats:italic>\n                    n\n                    <jats:sup>d<\/jats:sup>\n                  <\/jats:italic>\n                  log\n                  <jats:italic>n<\/jats:italic>\n                  ) bits in polynomial time,\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>(2)<\/jats:label>\n                <jats:p>\n                  <jats:sc>Max CSP\u0393<\/jats:sc>\n                  does not admit such a compression to \ud835\udcaa(\n                  <jats:italic>n<\/jats:italic>\n                  <jats:sup>d-\u03b5<\/jats:sup>\n                  ) bits unless NP \u2286 co-NP \/ poly.\n                <\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>\n          <jats:p>\n            Our reductions are based on interpreting constraints as multilinear polynomials combined with the framework of \u201cconstraint implementations\u201d, formerly used in the context of APX-hardness. As another application of our reductions, we reveal tight connections between optimal running times for solving\n            <jats:sc>Max CSP\u0393<\/jats:sc>\n            . More precisely, we show that obtaining a running time of the form \ud835\udcaa(2\n            <jats:sup>\n              (1-\u03b5)\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            ) for particular classes of\n            <jats:sc>Max CSP<\/jats:sc>\n            s is as hard as breaching this barrier for\n            <jats:sc>\n              Max\n              <jats:italic>d<\/jats:italic>\n              -SAT\n            <\/jats:sc>\n            for some\n            <jats:italic>d<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3624704","type":"journal-article","created":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T08:02:24Z","timestamp":1695715344000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Optimal Polynomial-Time Compression for Boolean Max CSP"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8204-1268","authenticated-orcid":false,"given":"Bart M. P.","family":"Jansen","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0968-8414","authenticated-orcid":false,"given":"Micha\u0142","family":"W\u0142odarczyk","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2024,3,12]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.83"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9428-7"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263424"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1993.336538"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.31"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_2_8_2","unstructured":"Andrei A. Bulatov Martin Grohe Phokion G. Kolaitis and Andrei A. Krokhin (Eds.). 2009. The Constraint Satisfaction Problem: Complexity and Approximability 25.10. - 30.10.2009. Dagstuhl Seminar Proceedings Vol. 09441. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik Germany. Retrieved from http:\/\/drops.dagstuhl.de\/portals\/09441\/"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2822891"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00660-y"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1087"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718546"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.03.003"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391290"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781107415157"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.4230\/DFU.Vol7.15301.7"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0189-9"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3349618"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2021.64"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.02.001"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2858787"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_55"},{"key":"e_1_3_2_25_2","series-title":"Dagstuhl Follow-Ups","volume-title":"The Constraint Satisfaction Problem: Complexity and Approximability","author":"Krokhin Andrei A.","year":"2017","unstructured":"Andrei A. Krokhin and Stanislav Zivny (Eds.). 2017. The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik. Retrieved from http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-003-3"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3389411"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.80"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.4230\/DFU.Vol7.15301.287"},{"key":"e_1_3_2_29_2","volume-title":"Perceptrons","author":"Minsky M.","year":"1969","unstructured":"M. Minsky and S. Papert. 1969. Perceptrons. MIT Press, Cambridge, MA."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)90477-6"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001597"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215917"},{"key":"e_1_3_2_34_2","volume-title":"Algorithms and Resource Requirements for Fundamental Problems","author":"Williams R. Ryan","year":"2007","unstructured":"R. Ryan Williams. 2007. Algorithms and Resource Requirements for Fundamental Problems. Ph. D. Dissertation. Carnegie Mellon University, USA. Advisor(s) Blum, Manuel. AAI3274191."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90020-8"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3624704","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3624704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:35:44Z","timestamp":1750178144000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3624704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3624704"],"URL":"https:\/\/doi.org\/10.1145\/3624704","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2024,3,12]]},"assertion":[{"value":"2021-10-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}