Optimal Inapproximability of Promise Equations over Finite Groups
Silvia Butti, Alberto Larrauri, Stanislav Živný · 2024
Read Optimal Inapproximability of Promise Equations over Finite Groups by Silvia Butti, Alberto Larrauri, Stanislav Živný (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01630.txt.
Description
Abstract A celebrated result of Håstad established that, for any constant ε > 0 \varepsilon>0 , it is NP-hard to find an assignment satisfying a ( 1 / | 𝒢 | + ε ) (1/|\mathscr{G}|+\varepsilon) -fraction of the constraints of a given 3 − LIN \operatorname{3-LIN} instance over an Abelian group 𝒢 \mathscr{G} even if one is promised that an
Catalog record
| CREATOR | Silvia Butti, Alberto Larrauri, Stanislav Živný |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 121 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01630
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal Inapproximability of Promise Equations over Finite Groups Thanks: An extended abstract of this work appeared in Proceedings of ICALP (A) 2025 [ BLŽ25 ] . This work was supported by UKRI EP/X024431/1 and done when SB and AL were at the University of Oxford. For the purpose of Open Access, the authors have applied a CC BY public copyright licence to any Author Accepted Manuscript version arising from this submission. All data is provided in full in the results section of this paper. Silvia Butti, Alberto Larrauri, Stanislav Živný Abstract A celebrated result of Håstad established that, for any constant ε > 0 \varepsilon>0 , it is NP-hard to find an assignment satisfying a ( 1 / | 𝒢 | + ε ) (1/|\mathscr{G}|+\varepsilon) -fraction of the constraints of a given 3 − LIN \operatorname{3-LIN} instance over an Abelian group 𝒢 \mathscr{G} even if one is promised that an assignment satisfying a ( 1 − ε ) (1-\varepsilon) -fraction of the constraints exists. Engebretsen, Holmerin, and Russell showed the same result for 3 − LIN \operatorname{3-LIN} instances over any finite (not necessarily Abelian) group. In other words, for almost-satisfiable instances of 3 − LIN \operatorname{3-LIN} the random assignment achieves an optimal approximation guarantee. We prove that the random assignment algorithm is still best possible under a stronger promise that the 3 − LIN \operatorname{3-LIN} instance is almost satisfiable over an arbitrarily more restrictive group. 1 Introduction The PCP theorem [ AS98 , ALM+98 , Din07 ] is one of the jewels of computational complexity and theoretical computer science more broadly [ AB09 ] . One of its equivalent statements is as follows: The maximum number of simultaneously satisfiable constraints of a Constraint Satisfaction Problem, or CSP for short, is NP-hard to approximate within some constant factor. That is, while NP-hardness of CSPs means that it is NP-hard to distinguish instances that are satisfiable from those that are unsatisfiable, the PCP theorem shows that there is an absolute constant \alpha<1 such that it is NP-hard to distinguish satisfiable CSP instances from those in which strictly fewer than an \alpha -fraction of the constraints can be simultaneously satisfied. Thus it is NP-hard to find an assignment that satisfies an \alpha -fraction of the constraints even if one is promised that a satisfying assignment exists. For some CSPs, as we shall see shortly, the optimal value of \alpha is known. A classic example of a CSP is 3-SAT, the satisfiability problem of CNF-formulas in which each clause contains 3 literals. The random assignment gives a method to find an assignment that satisfies a 7/8 -fraction of the clauses. Håstad famously showed that this is optimal in the following sense: For any constant \varepsilon>0 , it is NP-hard to find an assignment satisfying a (7/8+\varepsilon) -fraction of the clauses of a 3-SAT instance even if one is promised that a satisfying assignment exists [ Hås01 ] . Another classic CSP is \operatorname{3-LIN} , the problem of solving linear equations in 3 variables over the Boolean domain \{0,1\} . If all equations can be satisfied simultaneously then a satisfying assignment can be found in polynomial time by Gaussian elimination. What can be done if no satisfying assignment exists? As for 3-SAT, the random assignment gives a method to find a somewhat satisfying assignment, namely one that satisfies a 1/2 -fraction of the constraints. As it turns out, this is best possible even for instances of \operatorname{3-LIN} that are almost satisfiable. In detail, Håstad showed that for any constant \varepsilon>0 , it is NP-hard to find an assignment satisfying a (1/2+\varepsilon) -fraction of the constraints of a \operatorname{3-LIN} instance even if one is promised that an assignment satisfying a (1-\varepsilon) -fraction of the constraints exists. In fact, Håstad established optimal inapproximability results for \operatorname{3-LIN} over any finite Abelian group, not just \{0,1\} . This result was later extended by Engebretsen, Holmerin, and Russell to all finite groups [ EHR04 ] . Since these foundational works, Guruswami and Raghavendra [ GR09 ] showed NP-hardness of finding a barely satisfying assignment for a \operatorname{3-LIN} instance over the reals (and thus also over the integers) even if a nearly satisfying assignment is promised to exist over the integers. The same result was later established for \operatorname{2-LIN} for large enough cyclic groups [ OWZ15 ] . Khot and Moshkovitz [ KM13 ] studied inapproximability of \operatorname{3-LIN} over the reals. In this work, we strengthen the optimal inapproximability results for \operatorname{3-LIN} over finite groups by establishing NP-hardness of beating the random assignment threshold even if the instance is almost satisfiable in an arbitrarily more restrictive setting. Formally, this is captured by fixing (not one but) two groups and a homomorphism between them, following the framework of promise CSPs [ AGH17 , BBKO21 ] . In detail, (decision) promise CSPs [ BBKO21 ] can be seen as a qualitative form of approximation: Each constraint comes in two forms, a strong one and a weak one. The promise is that there is a solution satisfying all constraints in the strong form while the (potentially easier) goal is to find a solution satisfying all constraints in the weak form. An example of a strong vs. weak constraint on the same, say Boolean, domain is 1 -in- 3 vs NAE, where the former is \{(0,0,1),(0,1,0),(1,0,0)\} and the latter is \{(0,0,1),(0,1,0),(1,0,0),(1,1,0),(1,0,1),(0,1,1)\} . NAE is weaker as the relation contains more tuples. While these two constraint relations capture the well-known NP-hard problems of 1-in-3-SAT and Not-All-Equal-SAT respectively [ Sch78 ] , finding an NAE-assignment turns out to be doable in polynomial time under the promise that a 1-in-3-assignment exists [ BG21 ] ! 1 1 1 The algorithm involves solving an instance of \operatorname{3-LIN} over the integers and rounding positive integers to 1 and non-positive integers to 0 , demonstrating the importance of \operatorname{3-LIN} among promise CSPs. For constraints on different domains, the notion of strong vs. weak constraint is captured by a homomorphism between the (sets of all) constraint relations; in the example above, the homomorphism is just the identity function. The exact solvability of \operatorname{3-LIN} in the promise setting was resolved in [ LŽ25 ] . Recent work of Barto et al. [ BBK+24 ] initiated an algebraic investigation of (quantitative) approximation of promise CSPs. In the context of \operatorname{3-LIN} , here are two simple examples captured by this framework. First, let \mathscr{G} be a group and \mathscr{H} be a subgroup of \mathscr{G} . Given an almost-satisfiable system over the subgroup \mathscr{H} , maximise the number of satisfied equations over \mathscr{G} . Our results imply that beating the random assignment over \mathscr{H} is NP-hard. In the second example, consider a group \mathscr{G} , a normal subgroup \mathscr{H} , and an almost-satisfiable system over \mathscr{G} . The goal this time is to maximise the number of satisfied equations in the system over the quotient \mathscr{G}/\mathscr{H} . Our results show that doing better than the random assignment over \mathscr{G}/\mathscr{H} is NP-hard. More generally, going beyond subgroups and quotients of a given group, we fix two groups \mathscr{G}_{1} and \mathscr{G}_{2} and a group homomorphism \varphi from a subgroup \mathscr{H}_{1} of \mathscr{G}_{1} to a subgroup \mathscr{H}_{2} of \mathscr{G}_{2} with the property that \varphi extends to a group homomorphism