{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T05:40:17Z","timestamp":1768455617880,"version":"3.49.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Approximability and Proof Complexity"},{"DOI":"10.13039\/501100004063","name":"Knut and Alice Wallenberg Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004063","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,7,31]]},"abstract":"<jats:p>The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many Max-CSPs remain as hard to approximate as in the general case even when the factor graph is fixed (depending only on the size of the instance) and known in advance.<\/jats:p>\n          <jats:p>\n            Examples of results obtained for this restricted setting are:\n            <jats:list list-type=\"ordered\">\n              <jats:list-item>\n                <jats:label>(1)<\/jats:label>\n                <jats:p>Optimal inapproximability for Max-3-Lin and Max-3-Sat (H\u00e5stad, J.\u00a0ACM 2001).<\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>(2)<\/jats:label>\n                <jats:p>Approximation resistance for predicates supporting pairwise independent subgroups (Chan, J.\u00a0ACM 2016).<\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>(3)<\/jats:label>\n                <jats:p>Hardness of the \u201c(2+\u025b)-Sat\u201d problem and other Promise CSPs (Austrin et\u00a0al., SIAM J.\u00a0Comput.\u00a02017).<\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n            The main technical tool used to establish these results is a new way of folding the long code which we call \u201cfunctional folding\u201d.\n          <\/jats:p>","DOI":"10.1145\/3631119","type":"journal-article","created":{"date-parts":[[2023,12,15]],"date-time":"2023-12-15T06:26:45Z","timestamp":1702621605000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Optimal Inapproximability with Universal Factor Graphs"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8217-0158","authenticated-orcid":false,"given":"Per","family":"Austrin","sequence":"first","affiliation":[{"name":"KTH Royal Institute of Technology","place":["Sweden"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4294-8671","authenticated-orcid":false,"given":"Jonah","family":"Brown-Cohen","sequence":"additional","affiliation":[{"name":"Google DeepMind","place":["UK"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5379-345X","authenticated-orcid":false,"given":"Johan","family":"H\u00e5stad","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology","place":["Sweden"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7,26]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250818"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1006507"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462897"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.117"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316300"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2811255"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.18"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1007\/3-540-46135-3_21","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"Dalmau V\u00edctor","year":"2002","unstructured":"V\u00edctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi. 2002. Constraint satisfaction, bounded treewidth, and finite-variable logics. In Principles and Practice of Constraint Programming - CP 2002, Pascal Van Hentenryck (Ed.). Springer Berlin, Berlin, 310\u2013326."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_29"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.78"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22670-0_10"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.10"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/120882718"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2014.v010a014"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2014.274"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181879"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02128669"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754402"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797328847"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3631119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,26]],"date-time":"2025-07-26T09:28:13Z","timestamp":1753522093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3631119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,26]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,7,31]]}},"alternative-id":["10.1145\/3631119"],"URL":"https:\/\/doi.org\/10.1145\/3631119","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,26]]},"assertion":[{"value":"2021-03-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-17","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}