{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:08Z","timestamp":1740109328237,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T00:00:00Z","timestamp":1679875200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T00:00:00Z","timestamp":1679875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004063","name":"Knut och Alice Wallenbergs Stiftelse","doi-asserted-by":"publisher","award":["2016.0066"],"award-info":[{"award-number":["2016.0066"]}],"id":[{"id":"10.13039\/501100004063","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The factor graph of an instance of a constraint satisfaction problem with <jats:italic>n<\/jats:italic> variables and <jats:italic>m<\/jats:italic> constraints is the bipartite graph between [<jats:italic>m<\/jats:italic>] and [<jats:italic>n<\/jats:italic>] describing which variable appears in which constraints. Thus, an instance of a CSP is completely determined by its factor graph and the list of predicates. We show optimal inapproximability of Max-3-LIN over non-Abelian groups (both in the perfect completeness case and in the imperfect completeness case), even when the factor graph is fixed. Previous reductions which proved similar optimal inapproximability results produced factor graphs that were dependent on the input instance. Along the way, we also show that these optimal hardness results hold even when we restrict the linear equations in the Max-3-LIN instances to the form <jats:inline-formula><jats:alternatives><jats:tex-math>$$x\\cdot y\\cdot z = g$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>x<\/mml:mi>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:mi>y<\/mml:mi>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:mi>z<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>g<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>x<\/jats:italic>,\u00a0<jats:italic>y<\/jats:italic>,\u00a0<jats:italic>z<\/jats:italic> are the variables and <jats:italic>g<\/jats:italic> is a group element. We use representation theory and Fourier analysis over non-Abelian groups to analyze the reductions.<\/jats:p>","DOI":"10.1007\/s00453-023-01115-1","type":"journal-article","created":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T10:03:44Z","timestamp":1679911424000},"page":"2693-2734","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Max-3-Lin Over Non-abelian Groups with Universal Factor Graphs"],"prefix":"10.1007","volume":"85","author":[{"given":"Amey","family":"Bhangale","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksa","family":"Stankovi\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,27]]},"reference":[{"issue":"3","key":"1115_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"1115_CR2","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of NP. J. ACM 45(1), 70\u2013122 (1998)","journal-title":"J. ACM"},{"key":"1115_CR3","doi-asserted-by":"crossref","unstructured":"Austrin, P., Brown-Cohen, J., H\u00e5stad, J.: Optimal inapproximability with universal factor graphs. In: Proceedings of 51st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a0434\u2013453. (2021)","DOI":"10.1137\/1.9781611976465.27"},{"issue":"5","key":"1115_CR4","doi-asserted-by":"publisher","first-page":"1554","DOI":"10.1137\/15M1006507","volume":"46","author":"P Austrin","year":"2017","unstructured":"Austrin, P., Guruswami, V., H\u00e5stad, J.: (2+$$\\varepsilon $$)-Sat is NP-hard. SIAM J. Comput. 46(5), 1554\u20131573 (2017)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1115_CR5","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, pcps, and nonapproximability-towards tight results. SIAM J. Comput. 27(3), 804\u2013915 (1998)","journal-title":"SIAM J. Comput."},{"key":"1115_CR6","doi-asserted-by":"crossref","unstructured":"Bhangale, A., and Khot, S. Optimal inapproximability of satisfiable k-LIN over non-abelian groups. CoRR abs\/2009.02815 (2020). (to appear in STOC 2021)","DOI":"10.1145\/3406325.3451003"},{"key":"1115_CR7","doi-asserted-by":"crossref","unstructured":"Bul\u00edn, J., Krokhin, A.\u00a0A., Oprsal, J.: Algebraic approach to promise constraint satisfaction. In: Proceedings of 51st ACM Symposium on Theory of Computing (STOC), pp.\u00a0602\u2013613. (2019)","DOI":"10.1145\/3313276.3316300"},{"issue":"3","key":"1115_CR8","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/2873054","volume":"63","author":"SO Chan","year":"2016","unstructured":"Chan, S.O.: Approximation resistance from pairwise-independent subgroups. J. ACM 63(3), 27:1-27:32 (2016)","journal-title":"J. ACM"},{"issue":"3","key":"1115_CR9","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I Dinur","year":"2007","unstructured":"Dinur, I.: The PCP theorem by gap amplification. J. ACM 54(3), 12 (2007)","journal-title":"J. ACM"},{"issue":"1","key":"1115_CR10","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0304-3975(03)00401-8","volume":"312","author":"L Engebretsen","year":"2004","unstructured":"Engebretsen, L., Holmerin, J., Russell, A.: Inapproximability results for equations over finite groups. Theor. Comput. Sci. 312(1), 17\u201345 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"1115_CR11","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In Proceedings of 34th ACM Symposium on Theory of Computing (STOC), pp. 534\u2013543. (2002)","DOI":"10.1145\/509907.509985"},{"issue":"2","key":"1115_CR12","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268\u2013292 (1996)","journal-title":"J. ACM"},{"key":"1115_CR13","doi-asserted-by":"crossref","unstructured":"Feige, U., Jozeph, S.: Universal factor graphs. In: Proceedings of 39th International Colloquium of Automata, Languages and Programming (ICALP), Part I, vol.\u00a07391, pp.\u00a0339\u2013350. Springer (2012)","DOI":"10.1007\/978-3-642-31594-7_29"},{"issue":"4","key":"1115_CR14","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"1115_CR15","unstructured":"Jozeph, S.: Universal factor graphs for every NP-Hard Boolean CSP. In: Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques (APPROX\/RANDOM), vol.\u00a028 of LIPIcs, pp.\u00a0274\u2013283. (2014)"},{"key":"1115_CR16","doi-asserted-by":"crossref","unstructured":"Kothari, P.\u00a0K., Mori, R., O\u2019Donnell, R., Witmer, D.: Sum of squares lower bounds for refuting any CSP. In: Proceedings of 49th ACM Symposium on Theory of Computing (STOC), pp. 132\u2013145. (2017)","DOI":"10.1145\/3055399.3055485"},{"issue":"6","key":"1115_CR17","doi-asserted-by":"publisher","first-page":"1871","DOI":"10.1137\/080734042","volume":"40","author":"A Rao","year":"2011","unstructured":"Rao, A.: Parallel repetition in projection games and a concentration bound. SIAM J. Comput. 40(6), 1871\u20131891 (2011)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1115_CR18","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."},{"key":"1115_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9458-7","volume-title":"Linear Representations of Finite Groups","author":"J-P Serre","year":"1977","unstructured":"Serre, J.-P.: Linear Representations of Finite Groups. Springer, New York (1977)"},{"key":"1115_CR20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626265","volume-title":"Fourier Analysis on Finite Groups and Applications","author":"A Terras","year":"1999","unstructured":"Terras, A.: Fourier Analysis on Finite Groups and Applications. Cambridge University Press, Cambridge (1999)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01115-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01115-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01115-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T15:03:47Z","timestamp":1695395027000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01115-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,27]]},"references-count":20,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1115"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01115-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,3,27]]},"assertion":[{"value":"17 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}