2026-09-08T02:21:58Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:26419 2026-09-05T19:42:55Z ddc:004 open_access
Optimal Inapproximability of Generalized Linear Equations over a Finite Group Bhangale, Amey Zhang, Yezhou Constraint satisfaction problems inapproximability approximation algorithms non-abelian groups Fourier analysis Constraint satisfaction problems (CSPs) consist of a set of variables taking values from some finite domain and a set of local constraints on these variables. The objective is to find an assignment to the variables that maximizes the fraction of satisfied constraints. In this work, we study the CSP where the constraints are generalized linear equations over a finite group G. More specifically, for a given S βŠ† G, the constraints in this CSP are of the form addition of the values to the variables (similarly, product for non-abelian groups) belongs to the set S. We give an approximation algorithm for this problem on satisfiable instances and show that it is optimal for certain S assuming 𝐏≠ NP. This natural predicate is one of the very few known predicates that are approximation resistant on almost satisfiable instances, assuming 𝐏≠ NP, but admits a non-trivial approximation algorithm on satisfiable instances. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Amey Bhangale and Yezhou Zhang 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.30 urn:nbn:de:0030-drops-264193 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.30 eng https://creativecommons.org/licenses/by/4.0/legalcode