Abstract 1 Introduction References

Optimal Inapproximability of Promise Equations over Finite Groups

Silvia Butti ORCID Department of Computer Science, University of Oxford, UK Alberto Larrauri ORCID Department of Computer Science, University of Oxford, UK Stanislav Živný ORCID Department of Computer Science, University of Oxford, UK
Abstract

A celebrated result of Håstad established that, for any constant ε>0, it is NP-hard to find an assignment satisfying a (1/|𝒢|+ε)-fraction of the constraints of a given 3LIN instance over an Abelian group 𝒢 even if one is promised that an assignment satisfying a (1ε)-fraction of the constraints exists. Engebretsen, Holmerin, and Russell showed the same result for 3LIN instances over any finite (not necessarily Abelian) group. In other words, for almost-satisfiable instances of 3LIN 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 3LIN instance is almost satisfiable over an arbitrarily more restrictive group.

Keywords and phrases:
promise constraint satisfaction, approximation, linear equations
Category:
Track A: Algorithms, Complexity and Games
Funding:
Silvia Butti: UKRI EP/X024431/1.
Alberto Larrauri: UKRI EP/X024431/1.
Stanislav Živný: UKRI EP/X024431/1.
Copyright and License:
[Uncaptioned image] © Silvia Butti, Alberto Larrauri, and Stanislav Živný; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Design and analysis of algorithms
; Theory of computation Problems, reductions and completeness
Related Version:
Full Version: https://arxiv.org/abs/2411.01630 [18]
Acknowledgements:
We thank the anonymous reviewers for their feedback.
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

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 α<1 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 7/8-fraction of the clauses. Håstad famously showed that this is optimal in the following sense: For any constant ε>0, it is NP-hard to find an assignment satisfying a (7/8+ε)-fraction of the clauses of a 3-SAT instance even if one is promised that a satisfying assignment exists [25].

Another classic CSP is 3LIN, 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 3LIN that are almost satisfiable. In detail, Håstad showed that for any constant ε>0, it is NP-hard to find an assignment satisfying a (1/2+ε)-fraction of the constraints of a 3LIN instance even if one is promised that an assignment satisfying a (1ε)-fraction of the constraints exists. In fact, Håstad established optimal inapproximability results for 3LIN over any finite Abelian group, not just {0,1}. 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 3LIN 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 2LIN for large enough cyclic groups [35]. Khot and Moshkovitz [28] studied inapproximability of 3LIN over the reals.

In this work, we strengthen the optimal inapproximability results for 3LIN 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 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 [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 3LIN over the integers and rounding positive integers to 1 and non-positive integers to 0, demonstrating the importance of 3LIN 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 3LIN 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 3LIN, 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 𝒢1 and 𝒢2 and a group homomorphism φ from a subgroup 1 of 𝒢1 to a subgroup 2 of 𝒢2 with the property that φ extends to a group homomorphism from 𝒢1 to 𝒢2. Given an almost-satisfiable system of equations over 𝒢1 with constants in 1, the goal is to maximise the number of satisfied equations over 𝒢2 where the constants are interpreted in 2 via φ. Our main result establishes that doing better than the random assignment over 2 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 xyz=1. 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 3LIN over Abelian groups with a universal factor graph [4]. Similarly, Bhangale and Stankovic established optimal inapproximability of 3LIN over non-Abelian groups with a universal factor graph [14]. Second, unlike over Abelian groups, for 3LIN 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 3LIN instances over non-Abelian groups (whose approximation factor depends on the group 𝒢 and is 1/|𝒢| 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 3LIN, e.g. [11, 12, 13]. Third, going beyond 3LIN, 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 2LIN 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., P is 1 if P is true and 0 otherwise. As usual, [n] denotes the set {1,2,,n}.

We consider matrices whose sets of indices are arbitrary finite sets. Given two finite sets N and M, an N×M complex matrix A consists of a family of complex numbers Ai,j indexed by pairs iN, jM. Algebraic notions such as matrix product, trace, and transpose are defined in the natural way. Given an N1×N2 complex matrix A, and an M1×M2 complex matrix B, the tensor product AB is an (N1×M1)×(N2×M2) matrix, where (AB)(i,s)(j,t)=Ai,jBs,t for each iN1,jN2,sM1,tM2. The group of invertible N×N complex matrices (equipped with matrix multiplication and matrix inversion) is denoted by GL(N), and the set of N×M complex matrices is denoted by N×M.

Let X and Y be sets. We identify tuples 𝐲YX with functions 𝐲:XY, where the xth component of 𝐲 is given by 𝐲(x). Composition is defined from left to right in a natural way, i.e., if 𝐲YX and 𝐳ZY, then 𝐳𝐲XZ (also denoted just by 𝐳𝐲 when there is no ambiguity) is defined by (𝐳𝐲)(x)=𝐳(𝐲(x)) for each xX.

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 g𝒢, the right coset of in 𝒢 by g is the set g:={hgh}. The set of right cosets of in 𝒢 is denoted by \𝒢. Let N be a finite set. The Nth direct power of 𝒢, denoted by 𝒢N, is the group whose elements are N-tuples 𝐠𝒢N of elements from 𝒢, and where the group operation is taken component-wise, i.e., 𝐠𝐡(n)=𝐠(n)𝐡(n) for each nN. If 𝒢, we define (h𝐠)(n)=h𝐠(n) for each h and 𝐠𝒢N. With this notation, the notion of coset extends to include the right cosets of in 𝒢N in a natural way.

A homomorphism from a group 𝒢1 to a group 𝒢2 is a map φ:𝒢1𝒢2 which satisfies that φ(gh)=φ(g)φ(h) for every g,h𝒢1. The domain and image of φ are denoted Dom(φ) and Im(φ) respectively. Let N be a finite set, 𝒢i groups, i[2], i𝒢i, and φ:12 be a homomorphism. We say that a function f:𝒢1N𝒢2 is folded over φ if f(h𝐠)=φ(h)f(𝐠) for all h1 and 𝐠𝒢1N. Given an arbitrary function f:𝒢1N𝒢2 and a homomorphism between subgroups, there is a natural way to construct a folded function that resembles f. Fix an arbitrary representative from each right coset of 1 in 𝒢1N. For each 𝐠𝒢N, denote by 𝐠 the representative of 1𝐠, and let h𝐠1 be such that 𝐠=h𝐠𝐠. Then the folding of f over φ (with respect to this choice of representatives) is the map fφ:𝒢1N𝒢2 given by fφ(𝐠)=φ(h𝐠1)f(𝐠).

Fix a pair of disjoint finite sets D, E, called the label sets, and a subset ΠED of labeling functions. An instance of the Label Cover problem is a bipartite graph with vertex set UV and a labeling function πuvΠ for each edge {u,v} in the graph. The task is to decide whether there is a pair of assignments hD:UD, hE:VE that satisfies all the constraints, i.e., such that πuv(hD(u))=hE(v) for each edge {u,v}.

Given additionally a pair of rational constants 0<sc1, the gap version of this problem, known as the Gap Label Cover problem with completeness c and soundness s and denoted GLCD,E(c,s), is the problem of distinguishing instances where a c-fraction of the constraints can be satisfied from instances where not even an s-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 α>0 there exist finite sets D, E such that GLCD,E(1,α) 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 γ:𝒢GL(Nγ) for some finite set Nγ. We call |Nγ| the dimension of γ and write dimγ=|Nγ|. Given a pair of indices i,jNγ2, γi,j denotes the (i,j)-th entry of γ. The character of a representation γ, denoted by χγ, is its trace. The trivial representation, denoted 1, 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 Nβ×Nα complex matrix T such that α(g)=T1β(g)T for all g𝒢. In particular, dimα=dimβ. Similarly, the representation β is said to be a sub-representation of α if there is an invertible matrix T, such that T1α(g)T can be written as

(β(g)0)

for all g𝒢. 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 n satisfying that α is equivalent to a block diagonal representation with two diagonal blocks α1,α2, where (1) α1 is another block-diagonal representation consisting of n diagonal blocks equal to β, and (2) α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 2(𝒢) is the vector space of complex-valued functions over 𝒢, equipped with the following inner product:222Note the additional normalising factor of 1|𝒢| compared to [39].

F,H=1|𝒢|g𝒢F(g)H(g)¯.

Let 𝒢 be a group, and let F:𝒢 be a complex-valued function. Given γ𝒢^ and i,jNγ, the Fourier coefficient F^(γi,j) is defined as the product F,γi,j. The matrix entries of the representations γ𝒢^ form an orthogonal basis of 2(𝒢), 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

{γi,jγ𝒢^,i,jNγ}

is an orthogonal basis of 2(𝒢), and dimγγi,j2=1 for all γi,j. Moreover, the following hold:

  1. 1.

    Plancherel’s Theorem: Given F2(𝒢),

    F2=γ𝒢^,i,jNγdimγ|F^(γi,j)|2.
  2. 2.

    Fourier Inversion: Given F2(𝒢),

    F(g)=γ𝒢^,i,jNγdimγF^(γi,j)γi,j(g) for all g𝒢.

We also consider Fourier transforms of matrix-valued functions F:𝒢NF×NF. Given γ𝒢^ and indices i,jNγ, we define the NF×NF matrix F^(γi,j) as the one whose (s,t)-th entry is Fs,t^(γi,j) for each s,tNF. In other words,

F^(γi,j)=1|𝒢|g𝒢F(g)γi,j(g)¯.

Let N be a finite set. Given a pair of functions function F,H:𝒢N×N, we define their convolution FH by

(FH)(g):=1|𝒢|h𝒢F(h)H(h1g).

We will also need to perform Fourier analysis over powers of the form 𝒢D for a given group 𝒢 and finite set D. It is possible to identify 𝒢D^ with (𝒢^)D [39]. This way, an element ρ𝒢D^ is given by a tuple (ρd)dD where ρd𝒢^ for each dD in such a way that

ρ(𝐠)=dDρd(𝐠(d))

for all 𝐠𝒢D. Observe we use superscripts for the “components” of the representation ρ on the power group 𝒢D, rather than subscripts, which we utilise to denote matrix entries. The degree of ρ, written |ρ|, is the number of indices dD for which ρd is non-trivial.333This quantity is called “weight” in [23, 14].

1.2 Results

Let 𝒢1,𝒢2 be two groups and φ a group homomorphism with domain Dom(φ)𝒢1 and image Im(φ)𝒢2 that extends to a full homomorphism from 𝒢1 to 𝒢2. We shall refer to triples (𝒢1,𝒢2,φ) of this kind as templates. Further, let 0<sc1 be rational constants. We consider the problem 3LIN(𝒢1,𝒢2,φ,c,s) which asks, given a weighted system of linear equations with exactly three variables in each equation and constants in Dom(φ) that is c-satisfiable in 𝒢1, to decide whether there exists an s-approximation in 𝒢2, where the constants are interpreted through φ.

To be more precise, an instance to 3LIN(𝒢1,𝒢2,φ,c,s) over a set of variables X is a weighted systems of linear equations where each equation is of the form

xiyjzk=g

for some x,y,zX, gDom(φ), i,j,k{1,1}, 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 t[2], an assignment f:X𝒢t satisfies an equation xiyjzk=g in 𝒢t if f(x)if(y)jf(z)k=g for t=1, and f(x)if(y)jf(z)k=φ(g) for t=2. The task then is to accept if there is an assignment that satisfies a c-fraction (i.e., a fraction of total weight c) of equations in 𝒢1, and to reject if there is no assignment that satisfies an s-fraction of the equations in 𝒢2. It is easy to verify that, if (𝒢1,𝒢2,φ) is a template and sc, then the sets of accept and reject instances are, in fact, disjoint.4443LIN can be alternatively phrased as a promise constraint satisfaction problem, cf. [18] for details.

3LIN(𝒢1,𝒢2,φ,c,s) is trivially tractable when Im(φ)={1}, so we focus on the case where |Im(φ)|2. The main result of this paper is that 3LIN(𝒢1,𝒢2,φ,1ϵ,1/|Im(φ)|+δ) is NP-hard for all ϵ,δ>0 for which the problem is well-defined. This is achieved by a reduction from the Gap Label Cover problem with perfect completeness and soundness α=δ2/(4κ|𝒢1|κ|𝒢2|4), where κ=(log2δ2)/(log2(1ϵ)).

Theorem 3 (Main).

Let ϵ,δ be positive constants satisfying 1ϵ1/|Im(φ)|+δ. Then, 3LIN(𝒢1,𝒢2,φ,1ϵ,1/|Im(φ)|+δ) is NP-hard.

The hardness result in Theorem 3 is tight for many, but perhaps surprisingly not all, templates. We call a template (𝒢1,𝒢2,φ) cubic if for every hIm(φ) there is an element g𝒢2 satisfying g3=h. Theorem 3 is tight for cubic templates. Indeed, for these templates, the random assignment over Im(φ) achieves a 1/|Im(φ)| expected fraction of satisfied equations (and this can be derandomised, e.g., by the method of conditional expectations).

Theorem 4.

Let (𝒢1,𝒢2,φ) be a cubic template and 0<sc<1. Then the following holds: 3LIN(𝒢1,𝒢2,φ,c,s) is tractable if s1/|Im(φ)| and NP-hard otherwise.

Let us now turn to non-cubic templates. An equation is unsatisfiable if it is of the form x3=h or x3=h for some hDom(φ) such that g3φ(h) for all g𝒢2.555Note that, since φ extends to a homomorphism from 𝒢1 to 𝒢2, this also implies that g3h for all g𝒢1. 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 3LIN(𝒢1,𝒢2,φ,c,c/|Im(φ)|) that works even for non-cubic templates, which we describe next.

Given a weighted system of equations over (𝒢1,𝒢2,φ), 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 1c, then the instance cannot be c-satisfiable in 𝒢1, hence, reject. Otherwise, the random assignment over Im(φ) satisfies at least a 1/|Im(φ)|-fraction of the satisfiable equations over 𝒢2, which is at least a c/|Im(φ)|-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 (𝒢1,𝒢2,φ) be a non-cubic template and 0<sc<1. Then, 3LIN(𝒢1,𝒢2,φ,c,s) is tractable if s/c1/|Im(φ)| 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 3LIN(𝒢1,𝒢2,φ,1ϵ,1/|Im(φ)|+δ), 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 3LIN(𝒢1,𝒢2,φ,1ϵ,1/|Im(φ)|+δ) 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 (𝒢1,𝒢2,φ), and positive constants δ,ϵ>0 with 1/|Im(φ)|+δ1ϵ. We define 1=Dom(φ)𝒢1 and 2=Im(φ)𝒢2.

Our proof follows from a reduction from GLCD,E(1,α) where

α=δ24κ|𝒢1|κ|𝒢2|4,κ=log2δ2log2(1ϵ),

and D,E are chosen to be large enough so that GLCD,E(1,α) is NP-hard by the PCP theorem [2, 3, 37] (cf. Theorem 1). This reduction constructs an instance ΦΣ of 3LIN(𝒢1,𝒢2, φ,1ϵ,1/|2|+δ) for any given instance Σ of Gap Label Cover as described below.

Let UV be the underlying vertex set of Σ, D,E be the disjoint sets of labels, and πuv be the labeling functions. We fix representatives from each right coset in 1\𝒢1D and 1\𝒢1E. Given a tuple 𝐱 in either 𝒢1D or 𝒢1E we write 𝐱 for the representative of the coset 1𝐱. Let X={u𝐛|uU,𝐛𝒢1D}{v𝐚|vV,𝐚𝒢1E}. Then ΦΣ is the weighted system of equations over X that contains the equation

v𝐚u𝐛s1s1u𝐜s2s2=g𝐚 (1)

for each edge {u,v} of Σ, 𝐚𝒢1E, 𝐛𝒢1D, s1,s2{1,1}, where 𝐜 stands for 𝐛1(𝐚πuv)1𝝂 and 𝝂𝒢1D is a small perturbation factor. The element g𝐚 is chosen so that 𝐚=g𝐚𝐚. The weight of this equation in ΦΣ is the joint probability of the independent events described in Figure 1.

(1) The edge {u,v} is chosen uniformly at random among all edges of Σ. (2) The elements 𝐚 and 𝐛 are chosen uniformly at random from 𝒢1E and 𝒢1D respectively. (3) The element 𝝂𝒢1D is chosen so that for each dD, independently, 𝝂(d)=1𝒢1 with probability 1ϵ, and 𝝂(d) is selected uniformly at random from 𝒢1 with probability ϵ. (4) The signs s1,s2 are chosen uniformly at random from {1,1}.

Figure 1: The sampling procedure for ΦΣ.

Let us describe assignments of ΦΣ over 𝒢i for i=1,2. Formally, an assignment of ΦΣ over 𝒢i is a map h:X𝒢i. Such an assignment can be described by two families of maps A=(Av)vV from 𝒢1E to 𝒢i and B=(Bu)uU from 𝒢1D to 𝒢i by letting Av(𝐚)=h(v𝐚) for all vV,𝐚𝒢1E, and Bu(𝐛)=h(u𝐛) for all uU,𝐛𝒢1D. It will be more convenient to talk about the pair (A,B) rather than the map h itself, so we will write ΦΣ𝒢i(A,B) to refer to the proportion of equations satisfied by the assignment h. Let us give a more useful expression for ΦΣ𝒢i(A,B). When i=1, we can write

ΦΣ𝒢1(A,B)=𝔼uv,𝐚,𝐛,𝝂,s1,s2[Av(𝐚)Bu(𝐛s1)s1Bu((𝐛1(𝐚πuv)1𝝂)s2)s2=g𝐚],

where the expectation is taken over the probabilities described in Figure 1, and we use uv as a shorthand for an edge {u,v}. Folding the assignments Av over the identity on 1 and using the fact that (Av)id1(𝐚)=g𝐚1Av(𝐚), we obtain

ΦΣ𝒢1(A,B)= (2)
𝔼uv,𝐚,𝐛,𝝂,s1,s2[(Av)id1(𝐚)Bu(𝐛s1)s1Bu((𝐛1(𝐚πuv)1𝝂)s2)s2=1𝒢1].

Analogously, when i=2 and Av,Bu are families of maps to 𝒢2, we obtain a similar expression for ΦΣ𝒢2(A,B):

ΦΣ𝒢2(A,B)= (3)
𝔼uv,𝐚,𝐛,𝝂,s1,s2[(Av)φ(𝐚)Bu(𝐛s1)s1Bu((𝐛1(𝐚πuv)1𝝂)s2)s2=1𝒢2].

That is, a pair of assignments (A,B) satisfies an equation in ΦΣ if and only if the corresponding pair of assignments obtained by folding A (over id1 and φ respectively) maps the equation to the group identity (respectively, in 𝒢1 and 𝒢2). 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 D,E such that GLCD,E(1,α) 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 1-satisfiable. Then ΦΣ is (1ϵ)-satisfiable in 𝒢1.

Theorem 7 (Soundness).

Let Σ be a Gap Label Cover instance and ΦΣ be the system defined in (1). Suppose that ΦΣ is (1/|2|+δ)-satisfiable in 𝒢2. Then Σ is α-satisfiable, where α=δ2/(4κ|𝒢1|κ|𝒢2|4) and κ=(log2δ2)/(log2(1ϵ).

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 hD:UD, hE:VE. Then we find families A,B such that ΦΣ𝒢1(A,B)1ϵ by letting Av be the hE(v)-th projection and Bu be the hD(u)-th projection for each vV,uU. 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 A,B, satisfying

ΦΣ𝒢2(A,B)1|2|+δ. (4)

In view of (3), this inequality can be understood as a lower bound for the success probability of the following 3-query dictatorship test: Sample all parameters according to the distribution shown in Figure 1, and then query the values (Av)φ(𝐚), Bu(𝐛s1)s1, and Bu((𝐛1(𝐚πuv)1𝝂)s2)s2. 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 (Av)φ:𝒢1E𝒢2 and Bu:𝒢1D𝒢2 are “close” to dictators (i.e., projections) for each vV, uU. Then, this fact allows us to find a good solution to the starting Gap Label Cover instance Σ. Indeed, suppose that for each vV the map (Av)φ is the projection on the ev-th coordinate, and for each uU, the map Bu is the projection on the du-th coordinate. Then the assignment mapping v to ev and u to du for each vV,uU is a good solution for Σ. However, it is not clear how to extend this simple idea to the case where the maps (Av)φ,Bu are not projections.

In order to find a good solution for Σ in this general case, we first find suitable maps γ1,γ2:𝒢2 and analyse γ1(Av)φ, γ2Bu. Now, using the fact that (Av)φ and Bu are close to projections, we can prove that choosing the labels e,d for the vertices v,u according to the “low-degree influence” of the e-th coordinate in γ1(Av)φ and the d-th coordinate in γ2Bu 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 γ1,γ2. We define γ1=ωx,y, and γ2=ωy,z, where ω is some irreducible representation of 𝒢2, and x,y,z are suitable indices in Nω. In [23], the representation ω is a non-trivial representation chosen so that

|𝔼[χω((Av)φ(𝐚)Bu(𝐛s1)s1Bu((𝐛1(𝐚π)1𝝂)s2)s2)]|dimωδ.

Here the expectation is taken over the probability space described in Figure 1, and the dependence of π on the edge {u,v} is left implicit. In our case, rather than using the Fourier characters for choosing ω, we consider “penalized characters” χω~. We define χω~:𝒢2 as the map χωηω, where the penalty ηω is the multiplicity of the trivial representation in the restriction ω|2. This way, we pick ω𝒢2^ so that the previous inequality holds after replacing χω with χω~. Equivalently, we find ω satisfying

|𝔼[χω((Av)φ(𝐚)Bu(𝐛s1)s1Bu((𝐛1(𝐚π)1𝝂)s2)s2)]|dimωδ+ηω. (5)

The fact that such ω exists is a consequence of (4) together with

ω𝒢2^dimωηω=|𝒢2|/|2|,

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 𝒜=ω(Av)φ and the map :𝒢1D𝒢2 given by (𝐛)=𝔼s{1,1}ωBu(𝐛s)s, where s{1,1} is distributed uniformly.777Observe that the maps 𝒜 and depend on the hidden parameters v and u respectively. To show the soundness bound we consider the Fourier expansions of 𝒜 and in the expression

|tr𝔼[𝒜(𝐚)()((𝐚π)1𝝂)]|,

which is just a rearrangement of the left-hand-side in the previous inequality. More precisely, we look at the equivalent expression

|tr𝔼[(τ𝒢E^,s,tNτdimτ𝒜^(τs,t)τs,t(𝐚)) (6)
×(ρ𝒢D^,i,jNρdimρ()^(ρi,j)ρi,j((𝐚π)1𝝂))]|.

Our goal is to find a bound κ, independent of |D|,|E|, satisfying that the contribution to this expression of non-trivial representations τ,ρ of degree less than κ is at least dimωδ/2. 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

|tr𝔼[𝒜^(1)(ρ𝒢D^,i,jNρdimρ()^(ρi,j)ρi,j((𝐚π)1𝝂))]|ηω.

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 𝒜^(1) 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 F:𝒢1E𝒢2 is folded over φ, then the trace of (ωF)^(1) 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

|tr𝔼[(τ𝒢1E^,τ1s,tNτdimτ𝒜^(τs,t)τs,t(𝐚))×
(ρ𝒢1D^,|ρ|κi,jNρdimρ()^(ρi,j)ρi,j((𝐚π)1𝝂))]|(dimωδ)/2

for all κ(log2δ2)/log2(1ϵ). 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 dimωδ/2, in [18] we give a good randomised strategy to solve Σ. This strategy assigns the label eE to vV and the label dD to uU with probabilities

Pr(ve)=τ𝒢1E^,τe1s,tNτdimτ|𝒜x,y^(τs,t)|2|τ|

and

Pr(ud)=ρ𝒢1D^,ρd1i,jNρdimρ|y,z^(ρi,j)|2|ρ|,

where x,y,zNω are suitable indices [18]. These probabilities are supposed to capture the influence of the e-th and d-th coordinates on 𝒜x,y=ωx,y(Av)φ and y,z=ωy,z𝔼sBu(s)s respectively.888This is similar to the notion of influence in [10, 7]. (At this point it may be helpful to recall that Bu is a function from 𝒢1D to 𝒢2 and s is a sign sampled uniformly from {1,1}. Thus, Bu(s)s takes an element b𝒢1D and returns (Bu(bs))s.) This turns out to be a good randomised assignment for Σ. That is,

𝔼uv[dDPr(vπuv(d))Pr(ud)]α, (7)

where the expectation is taken uniformly over the edges {u,v} of Σ, and α is the soundness constant appearing in Theorem 7. We are being informal with the usage of the word “probability” here: the quantities Pr(ve) and Pr(ud) may add up to less than 1, 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 0. The probabilities Pr<(ve), Pr<(ud) are defined the same way as Pr(ve) and Pr(ud) but considering only representations τ,ρ of degree less than . These modified probabilities can be understood as the “low-degree influences” of each coordinate in 𝒜x,y and y,z. With this notation, in [18] we prove that (7) holds after replacing each assignment probability Pr with its truncated variant Pr<κ. In other words, we prove that

𝔼uv[dDρ𝒢1D^,ρd1|ρ|<κ,i,jNρτ𝒢1E^,τπuv(d)1|τ|<κ,s,tNτdimτ|𝒜x,y^(τs,t)|2|τ|dimρ|y,z^(ρi,j)|2|ρ|]α.

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 k-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 k-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-3-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 q-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 k- 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.