Optimal Inapproximability of Promise Equations over Finite Groups
Abstract
A celebrated result of Håstad established that, for any constant , it is NP-hard to find an assignment satisfying a -fraction of the constraints of a given instance over an Abelian group even if one is promised that an assignment satisfying a -fraction of the constraints exists. Engebretsen, Holmerin, and Russell showed the same result for instances over any finite (not necessarily Abelian) group. In other words, for almost-satisfiable instances of 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 instance is almost satisfiable over an arbitrarily more restrictive group.
Keywords and phrases:
promise constraint satisfaction, approximation, linear equationsCategory:
Track A: Algorithms, Complexity and GamesFunding:
Silvia Butti: UKRI EP/X024431/1.Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Design and analysis of algorithms ; Theory of computation Problems, reductions and completenessAcknowledgements:
We thank the anonymous reviewers for their feedback.Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
The PCP theorem [3, 2, 20] is one of the jewels of computational complexity and theoretical computer science more broadly [1]. 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 such that it is NP-hard to distinguish satisfiable CSP instances from those in which strictly fewer than an -fraction of the constraints can be simultaneously satisfied. Thus it is NP-hard to find an assignment that satisfies an -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 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 -fraction of the clauses. Håstad famously showed that this is optimal in the following sense: For any constant , it is NP-hard to find an assignment satisfying a -fraction of the clauses of a 3-SAT instance even if one is promised that a satisfying assignment exists [25].
Another classic CSP is , the problem of solving linear equations in 3 variables over the Boolean domain . 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 -fraction of the constraints. As it turns out, this is best possible even for instances of that are almost satisfiable. In detail, Håstad showed that for any constant , it is NP-hard to find an assignment satisfying a -fraction of the constraints of a instance even if one is promised that an assignment satisfying a -fraction of the constraints exists. In fact, Håstad established optimal inapproximability results for over any finite Abelian group, not just . This result was later extended by Engebretsen, Holmerin, and Russell to all finite groups [23]. Since these foundational works, Guruswami and Raghavendra [24] showed NP-hardness of finding a barely satisfying assignment for a 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 for large enough cyclic groups [35]. Khot and Moshkovitz [28] studied inapproximability of over the reals.
In this work, we strengthen the optimal inapproximability results for 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 [5, 8]. In detail, (decision) promise CSPs [8] 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 -in- vs NAE, where the former is
and the latter is
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 [38], finding an NAE-assignment turns out to be doable in polynomial time under the promise that a 1-in-3-assignment exists [15]!111The algorithm involves solving an instance of over the integers and rounding positive integers to and non-positive integers to , demonstrating the importance of 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 in the promise setting was resolved in [32].
Recent work of Barto et al. [9] considered (quantitative) approximation of promise CSPs. In the context of , here are two simple examples captured by this framework. First, let be a group and be a subgroup of . Given an almost-satisfiable system over the subgroup , maximise the number of satisfied equations over . Our results imply that beating the random assignment over is NP-hard. In the second example, consider a group , a normal subgroup , and an almost-satisfiable system over . The goal this time is to maximise the number of satisfied equations in the system over the quotient . Our results show that doing better than the random assignment over is NP-hard. More generally, going beyond subgroups and quotients of a given group, we fix two groups and and a group homomorphism from a subgroup of to a subgroup of with the property that extends to a group homomorphism from to . Given an almost-satisfiable system of equations over with constants in , the goal is to maximise the number of satisfied equations over where the constants are interpreted in via . Our main result establishes that doing better than the random assignment over is NP-hard, cf. Theorem 3. Thus we give an optimal inapproximability result for a natural and fundamental fragment of promise CSPs, systems of linear equations.
Other fragments of promise CSPs whose quantitative approximation has been studied includes almost approximate graph colouring [22, 21, 29, 26], approximate colouring [33], and approximate graph homomorphism [34]. Recent work of Brakensiek, Guruswami, and Sandeep [16] studied robust approximation of promise CSPs; in particular, they observed that Raghavendra’s celebrated theorem on approximate CSPs [36] applies to promise CSPs, which in combination with the work of Brown-Cohen and Raghavendra [17] gives an alternative framework for studying quantitative approximation of promise CSPs.
The general approach for establishing inapproximability of systems of equations, going back to [25, 23], can be seen as a reduction from another CSP that is hard to approximate. In this reduction, one initially transforms an instance of the original CSP to a system of equations of the form . To guarantee the soundness of this reduction, one needs to show that any assignment that beats the random assignment in the target system of equations can be transformed into a “good” assignment of the original instance. To do this it is necessary to rule out vacuous assignments (e.g., the assignment that sends all variables to the group identity) through a procedure called folding, which introduces constants in the system of equations. Afterwards, the soundness bounds are shown by performing Fourier analysis on certain functions derived from the system. Our proof follows this general approach. The main obstacle to applying the techniques of [23] directly is the fact that in our setting the constants lie in a proper subgroup of the ambient group, which precludes us from applying classical folding over groups. Instead, we use a weaker notion of folding. This, however, implies that in the soundness analysis we have to take care of functions whose Fourier expansion has non-zero value for the trivial term. To tackle this issue, we consider the behaviour of irreducible group representations when they are restricted to the subgroup of constants via Frobenius Reciprocity. We note that, as in the non-promise setting, the proof in the Abelian case is much simpler, particularly using that the set of characters of an Abelian group corresponds to its Pontryagin dual. Thus, much of the complicated machinery in the paper is to obtain the main result for all groups.
Before formal description of our results, we mention other related work. First, extending the work from [25], Austrin, Brown-Cohen, and Håstad established optimal inapproximability of over Abelian groups with a universal factor graph [4]. Similarly, Bhangale and Stankovic established optimal inapproximability of over non-Abelian groups with a universal factor graph [14]. Second, unlike over Abelian groups, for over non-Abelian groups finding a satisfying assignment is NP-hard even under the promise that one exists. There is a folklore randomised algorithm for satisfiable instances over non-Abelian groups (whose approximation factor depends on the group and is if is a so-called perfect group but can beat the naive random assignment for non-perfect groups). Bhangale and Khot showed that this algorithm is optimal [10], spawning a number of follow-up works going beyond , e.g. [11, 12, 13]. Third, going beyond , building on a long line of work Chan established optimal (up to a constant factor) NP-hardness for CSPs [19]. There are other works on various inapproximability notions for CSPs, e.g., [6, 30, 31]. We note that As in the non-promise setting, the proof in the Abelian case is much simpler, particularly using that the set of characters of an Abelian group corresponds to its Pontryagin dual. Thus, much of the complicated machinery in the paper could be avoided. Finally, we mention that Khot’s influential Unique Games Conjecture [27] postulates, in one of its equivalent forms, NP-hardness of finding a barely satisfying solution to a instance given that an almost-satisfying assignment exists (for a large enough domain size).
1.1 Preliminaries and notation
We use to denote the Iverson bracket; i.e., is 1 if is true and otherwise. As usual, denotes the set .
We consider matrices whose sets of indices are arbitrary finite sets. Given two finite sets and , an complex matrix consists of a family of complex numbers indexed by pairs , . Algebraic notions such as matrix product, trace, and transpose are defined in the natural way. Given an complex matrix , and an complex matrix , the tensor product is an matrix, where for each . The group of invertible complex matrices (equipped with matrix multiplication and matrix inversion) is denoted by , and the set of complex matrices is denoted by .
Let and be sets. We identify tuples with functions , where the component of is given by . Composition is defined from left to right in a natural way, i.e., if and , then (also denoted just by when there is no ambiguity) is defined by for each .
A subset of a group is called a subgroup of , denoted by , if equipped with the group operation of forms a group. Given a group , a subgroup of , and an element , the right coset of in by is the set . The set of right cosets of in is denoted by . Let be a finite set. The direct power of , denoted by , is the group whose elements are -tuples of elements from , and where the group operation is taken component-wise, i.e., for each . If , we define for each and . With this notation, the notion of coset extends to include the right cosets of in in a natural way.
A homomorphism from a group to a group is a map which satisfies that for every . The domain and image of are denoted and respectively. Let be a finite set, groups, , , and be a homomorphism. We say that a function is folded over if for all and . Given an arbitrary function and a homomorphism between subgroups, there is a natural way to construct a folded function that resembles . Fix an arbitrary representative from each right coset of in . For each , denote by the representative of , and let be such that . Then the folding of over (with respect to this choice of representatives) is the map given by .
Fix a pair of disjoint finite sets , , called the label sets, and a subset of labeling functions. An instance of the Label Cover problem is a bipartite graph with vertex set and a labeling function for each edge in the graph. The task is to decide whether there is a pair of assignments , that satisfies all the constraints, i.e., such that for each edge .
Given additionally a pair of rational constants , the gap version of this problem, known as the Gap Label Cover problem with completeness and soundness and denoted , is the problem of distinguishing instances where a -fraction of the constraints can be satisfied from instances where not even an -fraction of the constraints can be satisfied.
The hardness of Gap Label Cover with perfect completeness stated below is a consequence of the PCP theorem [2, 3] and the Parallel Repetition Theorem [37].
Theorem 1.
For every there exist finite sets , such that is NP-hard.
Fourier Analysis
We follow closely [39] for our main definitions and preliminary results. A representation of a group is a group homomorphism for some finite set . We call the dimension of and write . Given a pair of indices , denotes the -th entry of . The character of a representation , denoted by , is its trace. The trivial representation, denoted , maps all group elements to the number one (i.e., the one-dimensional identity matrix). A representation is said to be unitary if its image contains only unitary matrices.
We say that two representations and of some group are equivalent, written , if there is an invertible complex matrix such that for all . In particular, . Similarly, the representation is said to be a sub-representation of if there is an invertible matrix , such that can be written as
for all . The representation is said to be irreducible if all its sub-representations are equivalent to itself. If is irreducible, its multiplicity in is the non-negative integer satisfying that is equivalent to a block diagonal representation with two diagonal blocks , where (1) is another block-diagonal representation consisting of diagonal blocks equal to , and (2) does not have as a sub-representation.
Given a group , we use to denote some arbitrary and fixed complete set of inequivalent irreducible unitary representations of ; such a set exists by, e.g., [39, Proposition 1].
The space is the vector space of complex-valued functions over , equipped with the following inner product:222Note the additional normalising factor of compared to [39].
Let be a group, and let be a complex-valued function. Given and , the Fourier coefficient is defined as the product . The matrix entries of the representations form an orthogonal basis of , and allow us to perform Fourier analysis on this space, as stated in the following theorem [39, Theorem 2].
Theorem 2.
Let be a finite group. Then the set
is an orthogonal basis of , and for all . Moreover, the following hold:
-
1.
Plancherel’s Theorem: Given ,
-
2.
Fourier Inversion: Given ,
We also consider Fourier transforms of matrix-valued functions . Given and indices , we define the matrix as the one whose -th entry is for each . In other words,
Let be a finite set. Given a pair of functions function , we define their convolution by
We will also need to perform Fourier analysis over powers of the form for a given group and finite set . It is possible to identify with [39]. This way, an element is given by a tuple where for each in such a way that
for all . Observe we use superscripts for the “components” of the representation on the power group , rather than subscripts, which we utilise to denote matrix entries. The degree of , written , is the number of indices for which is non-trivial.333This quantity is called “weight” in [23, 14].
1.2 Results
Let be two groups and a group homomorphism with domain and image that extends to a full homomorphism from to . We shall refer to triples of this kind as templates. Further, let be rational constants. We consider the problem which asks, given a weighted system of linear equations with exactly three variables in each equation and constants in that is -satisfiable in , to decide whether there exists an -approximation in , where the constants are interpreted through .
To be more precise, an instance to over a set of variables is a weighted systems of linear equations where each equation is of the form
for some , , , and each equation has a non-negative rational weight. Without loss of generality, we assume that the weights are normalised, i.e., sum up to 1. For , an assignment satisfies an equation in if for , and for . The task then is to accept if there is an assignment that satisfies a -fraction (i.e., a fraction of total weight ) of equations in , and to reject if there is no assignment that satisfies an -fraction of the equations in . It is easy to verify that, if is a template and , then the sets of accept and reject instances are, in fact, disjoint.444 can be alternatively phrased as a promise constraint satisfaction problem, cf. [18] for details.
is trivially tractable when , so we focus on the case where . The main result of this paper is that is NP-hard for all for which the problem is well-defined. This is achieved by a reduction from the Gap Label Cover problem with perfect completeness and soundness , where .
Theorem 3 (Main).
Let be positive constants satisfying . Then, is NP-hard.
The hardness result in Theorem 3 is tight for many, but perhaps surprisingly not all, templates. We call a template cubic if for every there is an element satisfying . Theorem 3 is tight for cubic templates. Indeed, for these templates, the random assignment over achieves a expected fraction of satisfied equations (and this can be derandomised, e.g., by the method of conditional expectations).
Theorem 4.
Let be a cubic template and . Then the following holds: is tractable if and NP-hard otherwise.
Let us now turn to non-cubic templates. An equation is unsatisfiable if it is of the form or for some such that for all .555Note that, since extends to a homomorphism from to , this also implies that for all . Note that a template has unsatisfiable equations if and only if it is non-cubic. Note that the naive random assignment cannot achieve a positive approximation factor in systems of equations over non-cubic templates since the system could consist exclusively of unsatisfiable equations. However, there is a simple algorithm for that works even for non-cubic templates, which we describe next.
Given a weighted system of equations over , consider its set of unsatisfiable equations. Since extends to a full homomorphism, if the total weight of the set of unsatisfiable equations is more than , then the instance cannot be -satisfiable in , hence, reject. Otherwise, the random assignment over satisfies at least a -fraction of the satisfiable equations over , which is at least a -fraction of the entire system. It is a simple corollary of Theorem 3 that this algorithm is optimal for non-cubic groups, leading to the following result. Details are deferred to the full version of this paper [18].
Theorem 5.
Let be a non-cubic template and . Then, is tractable if and NP-hard otherwise.
The structure of the paper is as follows. The rest of this section gives a sketch of the main proof: In Section 1.3 we present the reduction from Gap Label Cover to , and in Section 1.4 we give an overview of the techniques used in the analysis of this reduction and of the main challenges that arise in extending previous work to the promise setting. The rest of the paper then gives the main ideas of the technical details. All details are deferred to the full version of this paper [18], which also relates our results to a recent theory of Barto et al. [9], who developed a systematic approach to study (in)approximability of promise CSPs, which includes approximability of promise linear equations, from the viewpoint of universal algebra. In particular, we show in [18] that the proof of Theorem 3 implies that the collection of symmetries666called the valued minion of plurimorphisms in [9]. of can be mapped homomorphically to the collection of symmetries of Gap Label Cover, a condition that, based on the algebraic theory from [9], is known to guarantee NP-hardness of the former problem.
1.3 Reduction
For the rest of the section we outline the proof of our main result, Theorem 3. From now on we fix a template , and positive constants with . We define and .
Our proof follows from a reduction from where
and are chosen to be large enough so that is NP-hard by the PCP theorem [2, 3, 37] (cf. Theorem 1). This reduction constructs an instance of for any given instance of Gap Label Cover as described below.
Let be the underlying vertex set of , be the disjoint sets of labels, and be the labeling functions. We fix representatives from each right coset in and . Given a tuple in either or we write for the representative of the coset . Let . Then is the weighted system of equations over that contains the equation
(1) |
for each edge of , , , , where stands for and is a small perturbation factor. The element is chosen so that . The weight of this equation in is the joint probability of the independent events described in Figure 1.
() The edge is chosen uniformly at random among all edges of . () The elements and are chosen uniformly at random from and respectively. () The element is chosen so that for each , independently, with probability , and is selected uniformly at random from with probability . () The signs are chosen uniformly at random from .
Let us describe assignments of over for . Formally, an assignment of over is a map . Such an assignment can be described by two families of maps from to and from to by letting for all , and for all . It will be more convenient to talk about the pair rather than the map itself, so we will write to refer to the proportion of equations satisfied by the assignment . Let us give a more useful expression for . When , we can write
where the expectation is taken over the probabilities described in Figure 1, and we use as a shorthand for an edge . Folding the assignments over the identity on and using the fact that , we obtain
(2) | ||||
Analogously, when and are families of maps to , we obtain a similar expression for :
(3) | ||||
That is, a pair of assignments satisfies an equation in if and only if the corresponding pair of assignments obtained by folding (over and respectively) maps the equation to the group identity (respectively, in and ). Thus, folding allows us to focus exclusively on the identity terms in these expectations, which will be useful in the analysis of the reduction.
Theorem 3 follows from our completeness and soundness bounds for , stated in the next results, using the fact that by Theorem 1, there are finite sets such that is NP-hard for the value of chosen in Theorem 7 below. The proofs of the completeness and soundness bounds can be found in the full version [18].
Theorem 6 (Completeness).
Let be a Gap Label Cover instance and be the system defined in (1). Suppose that is -satisfiable. Then is -satisfiable in .
Theorem 7 (Soundness).
Let be a Gap Label Cover instance and be the system defined in (1). Suppose that is -satisfiable in . Then is -satisfiable, where and .
1.4 Proof Outline
The main difficulty in proving the correctness of our reduction lies in showing the soundness bound (Theorem 7). The completeness result (Theorem 6) is relatively straightforward and follows as in [23]. In summary, suppose the Gap Label Cover instance is satisfied by a pair of assignments , . Then we find families such that by letting be the -th projection and be the -th projection for each . As usual, the noise introduced by the perturbation factor is what forces us to give up perfect completeness.
The idea behind our soundness analysis has appeared many times in the literature (e.g., [25, 23, 10]), but the approach taken in [23] is the most similar to ours. Suppose that there are assignments , satisfying
(4) |
In view of (3), this inequality can be understood as a lower bound for the success probability of the following -query dictatorship test: Sample all parameters according to the distribution shown in Figure 1, and then query the values , , and . The test is passed if the product of the three values is the group identity, and failed otherwise. The soundness proof consists in showing that (4) implies that the functions and are “close” to dictators (i.e., projections) for each , . Then, this fact allows us to find a good solution to the starting Gap Label Cover instance . Indeed, suppose that for each the map is the projection on the -th coordinate, and for each , the map is the projection on the -th coordinate. Then the assignment mapping to and to for each is a good solution for . However, it is not clear how to extend this simple idea to the case where the maps are not projections.
In order to find a good solution for in this general case, we first find suitable maps and analyse , . Now, using the fact that and are close to projections, we can prove that choosing the labels for the vertices according to the “low-degree influence” of the -th coordinate in and the -th coordinate in yields a good randomised assignment of .
This overview so far also applies to the soundness analysis of [23]. Let us give more detail and highlight the main differences that sets our work apart. The first important difference has to do with the choice of . We define , and , where is some irreducible representation of , and are suitable indices in . In [23], the representation is a non-trivial representation chosen so that
Here the expectation is taken over the probability space described in Figure 1, and the dependence of on the edge is left implicit. In our case, rather than using the Fourier characters for choosing , we consider “penalized characters” . We define as the map , where the penalty is the multiplicity of the trivial representation in the restriction . This way, we pick so that the previous inequality holds after replacing with . Equivalently, we find satisfying
(5) |
The fact that such exists is a consequence of (4) together with
which follows from the Frobenius Reciprocity Theorem, as shown in detail in [18]. This additional factor of is crucial to our soundness analysis, as we will see.
Define the map and the map given by , where is distributed uniformly.777Observe that the maps and depend on the hidden parameters and respectively. To show the soundness bound we consider the Fourier expansions of and in the expression
which is just a rearrangement of the left-hand-side in the previous inequality. More precisely, we look at the equivalent expression
(6) | ||||
Our goal is to find a bound , independent of , satisfying that the contribution to this expression of non-trivial representations of degree less than is at least . This is achieved by controlling the contribution of the trivial term and the contribution of high-degree terms. The second main difference of our soundness analysis compared to [23] is our handling of the trivial term. In the full version [18] we prove that
In the non-promise setting, this bound is not necessary. Roughly, under the stronger notion of folding used in [23], it is possible to show that vanishes. Our weaker notion of folding does not allow us to prove the same result, but we are still able to leverage folding to obtain the above bound. This mismatch with [23] is the reason why the extra term was required in (5). The key insight in the proof of the inequality above is that if is folded over , then the trace of is at most in absolute value.
Our analysis of high-degree terms is in the same spirit as previous works that show hardness of approximation in the imperfect completeness setting. In [18] we prove that
for all . The essential idea is that the “noise vector” has a smoothing effect that limits the contribution of high-degree terms in (6).
Finally, having established that the contribution of non-trivial terms of degree less than in (6) is at least , in [18] we give a good randomised strategy to solve . This strategy assigns the label to and the label to with probabilities
and
where are suitable indices [18]. These probabilities are supposed to capture the influence of the -th and -th coordinates on and respectively.888This is similar to the notion of influence in [10, 7]. (At this point it may be helpful to recall that is a function from to and is a sign sampled uniformly from . Thus, takes an element and returns .) This turns out to be a good randomised assignment for . That is,
(7) |
where the expectation is taken uniformly over the edges of , and is the soundness constant appearing in Theorem 7. We are being informal with the usage of the word “probability” here: the quantities and may add up to less than , but this is easily fixed by normalising, or by letting our strategy default to the uniform assignment with some positive probability.
Let us give some more detail. More precisely, in the full version [18] we show that truncating our assignment probabilities to terms of degree less than is enough to satisfy this last inequality. Let . The probabilities , are defined the same way as and but considering only representations of degree less than . These modified probabilities can be understood as the “low-degree influences” of each coordinate in and . With this notation, in [18] we prove that (7) holds after replacing each assignment probability with its truncated variant . In other words, we prove that
This shows that our proposed strategy produces a good randomised assignment for and completes the soundness proof.
References
- [1] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.
- [2] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. doi:10.1145/278298.278306.
- [3] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, 1998. doi:10.1145/273865.273901.
- [4] Per Austrin, Jonah Brown-Cohen, and Johan Håstad. Optimal inapproximability with universal factor graphs. ACM Trans. Algorithms, 2023. doi:10.1145/3631119.
- [5] Per Austrin, Venkatesan Guruswami, and Johan Håstad. (2+)-Sat is NP-hard. SIAM J. Comput., 46(5):1554–1573, 2017. doi:10.1137/15M1006507.
- [6] Per Austrin and Johan Håstad. On the usefulness of predicates. ACM Trans. Comput. Theory, 5(1):1:1–1:24, 2013. doi:10.1145/2462896.2462897.
- [7] Per Austrin and Elchanan Mossel. Approximation resistant predicates from pairwise independence. Computational Complexity, 18(2):249–271, 2009. doi:10.1007/s00037-009-0272-6.
- [8] Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. J. ACM, 68(4):28:1–28:66, 2021. doi:10.1145/3457606.
- [9] Libor Barto, Silvia Butti, Alexandr Kazda, Caterina Viola, and Stanislav Živný. Algebraic approach to approximation. In Proc. 39th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’24), pages 10:1–10:14. ACM, 2024. doi:10.1145/3661814.3662076.
- [10] Amey Bhangale and Subhash Khot. Optimal Inapproximability of Satisfiable -LIN over Non-Abelian Groups. In Proc. 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC’21), pages 1615–1628. ACM, 2021. doi:10.1145/3406325.3451003.
- [11] Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable -CSPs: I. In Proc. 54th Annual ACM Symposium on Theory of Computing (STOC’22), pages 976–988. ACM, 2022. doi:10.1145/3519935.3520028.
- [12] Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable k-CSPs: II. In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC’23), pages 632–642. ACM, 2023. doi:10.1145/3564246.3585120.
- [13] Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable k-CSPs: III. In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC’23), pages 643–655. ACM, 2023. doi:10.1145/3564246.3585121.
- [14] Amey Bhangale and Aleksa Stankovic. Max--Lin Over Non-abelian Groups with Universal Factor Graphs. Algorithmica, 85(9):2693–2734, 2023. doi:10.1007/S00453-023-01115-1.
- [15] Joshua Brakensiek and Venkatesan Guruswami. Promise constraint satisfaction: Algebraic structure and a symmetric Boolean dichotomy. SIAM J. Comput., 50(6):1663–1700, 2021. doi:10.1137/19M128212X.
- [16] Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. SDPs and robust satisfiability of promise CSP. In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC’23), pages 609–622, 2023. doi:10.1145/3564246.3585180.
- [17] Jonah Brown-Cohen and Prasad Raghavendra. Combinatorial optimization algorithms via polymorphisms. CoRR, 2015. arXiv:1501.01598.
- [18] Silvia Butti, Alberto Larrauri, and Stanislav Živný. Optimal inapproximability of promise equations over finite groups. CoRR, 2024. doi:10.48550/arXiv.2411.01630.
- [19] Siu On Chan. Approximation resistance from pairwise-independent subgroups. J. ACM, 63(3):27:1–27:32, 2016. doi:10.1145/2873054.
- [20] Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. doi:10.1145/1236457.1236459.
- [21] Irit Dinur, Subhash Khot, Will Perkins, and Muli Safra. Hardness of finding independent sets in almost 3-colorable graphs. In Proc. 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS’10), pages 212–221. IEEE Computer Society, 2010. doi:10.1109/FOCS.2010.84.
- [22] Lars Engebretsen and Jonas Holmerin. More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. Random Struct. Algorithms, 33(4):497–514, 2008. doi:10.1002/RSA.20226.
- [23] Lars Engebretsen, Jonas Holmerin, and Alexander Russell. Inapproximability results for equations over finite groups. Theor. Comput. Sci., 312(1):17–45, 2004. doi:10.1016/S0304-3975(03)00401-8.
- [24] Venkatesan Guruswami and Prasad Raghavendra. Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers. ACM Trans. Comput. Theory, 1(2):6:1–6:20, 2009. doi:10.1145/1595391.1595393.
- [25] Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. doi:10.1145/502090.502098.
- [26] Yahli Hecht, Dor Minzer, and Muli Safra. NP-Hardness of Almost Coloring Almost 3-Colorable Graphs. In Proc. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM’23), volume 275 of LIPIcs, pages 51:1–51:12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.APPROX/RANDOM.2023.51.
- [27] Subhash Khot. On the power of unique 2-prover 1-round games. In Proc. 34th Annual ACM Symposium on Theory of Computing (STOC’02), pages 767–775, 2002. doi:10.1145/509907.510017.
- [28] Subhash Khot and Dana Moshkovitz. NP-Hardness of Approximately Solving Linear Equations over Reals. SIAM J. Comput., 42(3):752–791, 2013. doi:10.1137/110846415.
- [29] Subhash Khot and Rishi Saket. Hardness of finding independent sets in almost -colorable graphs. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’12), pages 380–389. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.75.
- [30] Subhash Khot, Madhur Tulsiani, and Pratik Worah. A characterization of strong approximation resistance. In Proc. 46th Symposium on Theory of Computing (STOC’14), pages 634–643. ACM, 2014. doi:10.1145/2591796.2591817.
- [31] Subhash Khot, Madhur Tulsiani, and Pratik Worah. The complexity of somewhat approximation resistant predicates. In Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP’14), volume 8572 of Lecture Notes in Computer Science, pages 689–700. Springer, 2014. doi:10.1007/978-3-662-43948-7_57.
- [32] Alberto Larrauri and Stanislav Živný. Solving promise equations over monoids and groups. In Proc. 51st International Colloquium on Automata, Languages, and Programming (ICALP’24), volume 297 of LIPIcs, pages 146:1–146:18, 2024. doi:10.4230/LIPIcs.ICALP.2024.146.
- [33] Tamio-Vesa Nakajima and Stanislav Živný. Maximum - vs. -colourings of graphs. CoRR, 2023. arXiv:2311.00440.
- [34] Tamio-Vesa Nakajima and Stanislav Živný. Maximum bipartite vs. triangle-free subgraph. In Proc. 52nd International Colloquium on Automata, Languages, and Programming (ICALP’25), 2025. arXiv:2406.20069.
- [35] Ryan O’Donnell, Yi Wu, and Yuan Zhou. Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups. ACM Trans. Comput. Theory, 7(2):9:1–9:16, 2015. doi:10.1145/2751322.
- [36] Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proc. 40th Annual ACM Symposium on Theory of Computing (STOC’08), pages 245–254, 2008. doi:10.1145/1374376.1374414.
- [37] Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. doi:10.1137/S0097539795280895.
- [38] Thomas Schaefer. The complexity of satisfiability problems. In Proc. 10th Annual ACM Symposium on the Theory of Computing (STOC’78), pages 216–226, 1978. doi:10.1145/800133.804350.
- [39] Audrey Terras. Fourier Transform and Representations of Finite Groups, pages 240–266. London Mathematical Society Student Texts. Cambridge University Press, 1999.