Optimal Inapproximability of Generalized Linear Equations over a Finite Group

Bhangale, Amey; Zhang, Yezhou

doi:10.4230/LIPIcs.ICALP.2026.30

Optimal Inapproximability of Generalized Linear Equations over a Finite Group

Amey Bhangale

Department of Computer Science and Engineering, University of California, Riverside, CA, USA Yezhou Zhang²²2Corresponding author

Department of Computer Science and Engineering, University of California, Riverside, CA, USA

Abstract

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\subseteq 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 $\mathbf{P}\neq\mathbf{NP}$ .

This natural predicate is one of the very few known predicates that are approximation resistant on almost satisfiable instances, assuming $\mathbf{P}\neq\mathbf{NP}$ , but admits a non-trivial approximation algorithm on satisfiable instances.

Keywords and phrases:

Constraint satisfaction problems, inapproximability, approximation algorithms, non-abelian groups, Fourier analysis

Category:

Track A: Algorithms, Complexity and Games

Funding:

Amey Bhangale: Supported by the Hellman Fellowship award and NSF CAREER award 2440882.

Yezhou Zhang: Supported by the Hellman Fellowship award and NSF CAREER award 2440882.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Problems, reductions and completeness

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Constraint satisfaction problems (CSPs) are one of the most fundamental problems in theoretical computer science. A Max- $P$ -CSP instance $\varphi$ for a given predicate $P:\Sigma^{k}\rightarrow\{0,1\}$ consists of a set of variables $x_{1},x_{2},\ldots,x_{n}$ taking values from the domain $\Sigma$ and a collection of constraints $C_{1},C_{2},\ldots,C_{m}$ where each $C_{i}$ consists of a constraint of the form $P(x_{i_{1}},x_{i_{2}},\ldots,x_{i_{k}})$ . The constraints might involve literals instead of just the variables. The objective is to assign values to the variables that maximize the fraction of satisfied constraints from $\varphi$ . An $\alpha$ -approximation for Max- $P$ -CSP is an algorithm that, given an instance $\varphi$ of Max- $P$ -CSP, outputs an assignment that satisfies at least $\alpha\cdot\mathrm{OPT}$ , where $\mathrm{OPT}$ is the optimal value of the instance $\varphi$ .

A systematic study of the complexity of CSPs was started by Schaefer in 1978 [36], who showed that for every predicate $P$ over a $2$ -element set, the problem $P$ -CSP is either solvable in polynomial time or is $\mathbf{NP}$ -complete. A famous dichotomy conjecture of Feder and Vardi [17, 18], which was resolved recently in huge breakthroughs by Bulatov [11] and Zhuk [38] independently, states that for every predicate $P$ , checking the satisfiability of a $P$ -CSP is either in $\mathbf{P}$ or is $\mathbf{NP}$ -complete. However, when it comes to approximation algorithms for Max- $P$ -CSP, the question is wide open.

The optimal approximability results for Max- $P$ -CSP for various predicates $P$ are known starting with the seminal work of [24]. Håstad showed that Max-3SAT, where the predicate is over a Boolean alphabet and is an OR of three literals, is $\mathbf{NP}$ -hard to approximate within a factor of $\frac{7}{8}+\varepsilon$ for every $\varepsilon>0$ . The above hardness result also holds even if the given instance is guaranteed to have an assignment with value $1$ . It is also easy to get a $\frac{7}{8}$ -approximation algorithm for Max-3SAT – for each variable, pick a random value from $\{0,1\}$ . This algorithm satisfies $\frac{7}{8}$ -fraction of the constraints in expectation. It is also easy to derandomize this algorithm by the method of conditional expectation. Thus, the hardness result is optimal. In the same work on the optimal hardness of Max-3SAT, Håstad [24] also studied the inapproximability of Max-3LIN over an abelian group $G$ . In Max-3LIN over a group $G$ , the variables take values from the group $(G,+)$ , and constraints are of the type $x_{i_{1}}+x_{i_{2}}+x_{i_{3}}=c$ for some $c\in G$ . If the given instance of Max-3LIN is fully satisfiable, then it is known [21] that the satisfying assignment can be found in polynomial time using techniques similar to Gaussian elimination. Furthermore, a random assignment to the variables satisfies $\frac{1}{|G|}$ fraction of the constraints in expectation. Håstad [24] showed that this algorithm is optimal for general instances.

The Max-3LIN over a non-abelian group $(G,\text{ $\bullet$}\hskip 2.0pt)$ is another interesting problem. Unlike the abelian group case, here, Goldmann and Russell showed [21] that it is $\mathbf{NP}$ -complete to check the satisfiability of a given instance for every non-abelian group $G$ . Engebretsen, Holmerin, and Russell gave [16] similar inapproximability results as in the case of abelian groups. More specifically, they showed that for every $\varepsilon>0$ , if an instance of Max-3LIN over a non-abelian group $(G,\text{ $\bullet$}\hskip 2.0pt)$ is given with value at least $1-\varepsilon$ , then it is $\mathbf{NP}$ -hard to find an assignment that satisfies at least $\frac{1}{|G|}+\varepsilon$ fraction of the constraints. There is, however, a better than $\frac{1}{|G|}$ approximation algorithm for certain groups on satisfiable instances. It is folklore to get a $\frac{1}{|[G,G]|}$ -approximation algorithm for Max-3LIN over a non-abelian group $(G,\text{ $\bullet$}\hskip 2.0pt)$ on satisfiable instances, where $[G,G]$ is the commutator subgroup of $G$ . A commutator of two group elements $g$ and $h$ is a group element $g^{-1}\text{ $\bullet$}\hskip 2.0pth^{-1}\text{ $\bullet$}\hskip 2.0ptg\text{ % $\bullet$}\hskip 2.0pth$ , and a commutator subgroup $[G,G]$ is the subgroup generated by all the commutators of the group $G$ . Recently, Bhangale and Khot [4] showed that this algorithm is optimal on satisfiable instances assuming $\mathbf{P}\neq\mathbf{NP}$ .

Given these approximation algorithms and inapproximability results concerning Max-3LIN, it is natural to ask what role the abelian nature of a group $G$ plays in such results. In this work, we study a generalized version of the Max-3LIN problem, denoted by $\text{Max-E$k$-LIN}_{S}(G)$ , as defined below.

Fix a group $(G,\text{ $\bullet$}\hskip 2.0pt)$ and a subset $S\subseteq G$ . In the instance of $\text{Max-E$k$-LIN}_{S}(G)$ , the variables take values from $G$ . A literal of a variable $x$ is given by $(g\text{ $\bullet$}\hskip 2.0ptx)$ for some $g\in G$ .

Definition 1 ( $\text{Max-E$k$-LIN}_{S}(G)$ ).

Consider a multiset of linear equations $(C_{1},C_{2},\dots,C_{m})$ over variables $\{x_{1},x_{2},\dots,x_{n}|x_{i}\in G\}$ for a group $G$ . Each constraint consists of a tuple of exactly $k$ literals and will be considered satisfied when their sum/product over $G$ is in $S\subseteq G$ . The $\text{Max-E$k$-LIN}_{S}(G)$ problem is to find an assignment to $\{x_{1},x_{2},\dots,x_{n}\}$ that maximizes the number of satisfied constraints.

Observe that the problem Max-3LIN over a group $G$ that was discussed earlier is $\text{Max-E$k$-LIN}_{\{1_{G}\}}(G)$ where $1_{G}$ is the identity element of the group $G$ . In $\text{Max-E$k$-LIN}_{S}(G)$ , we allow more satisfying assignments in the predicate, i.e, ignoring the literals for simplicity, the condition that a tuple $(a,b,c)$ satisfies a given constraint depends on the value of $a\text{ $\bullet$}\hskip 2.0ptb\text{ $\bullet$}\hskip 2.0ptc$ , and hence we call the predicate a generalized linearity predicate over $G$ .³³3This nomenclature was also used by Chattopadhyay and Wigderson [13] to describe similar predicates.

Approximation Algorithm for $\text{Max-E$3$-LIN}_{S}(G)$

To keep things simple, we restrict to the setting when $G$ is an abelian group for this discussion. We start with a simple approximation algorithm for $\text{Max-E$3$-LIN}_{S}(G)$ . Let $\Phi$ be an instance of $\text{Max-E$3$-LIN}_{S}(G)$ with constraints set $(C_{1},C_{2},\ldots,C_{m})$ over the variables $X=\{x_{1},x_{2},\ldots,x_{n}\}$ . Here, the constraint $C_{i}$ is of the form

(a_{i_{1}}+x_{i_{1}})+(a_{i_{2}}+x_{i_{2}})+(a_{i_{3}}+x_{i_{3}})\in S.

One can try to replace checking this condition by a linear equation over a certain abelian group, hoping to solve this system using Gaussian elimination, and from this solution get a non-trivial solution to the original instance. The basic algorithmic idea is to relax the constraint by passing to a quotient group. Suppose $H\leqslant G$ is a subgroup such that $S\subseteq g+H$ for some $g\in G$ , and let $Q:=G/H$ . Then the above constraint implies

\displaystyle([a_{i_{1}}]_{Q}+[x_{i_{1}}]_{Q})+([a_{i_{2}}]_{Q}+[x_{i_{2}}]_{Q% })+([a_{i_{3}}]_{Q}+[x_{i_{3}}]_{Q})=0_{Q},

(1)

Thus, we convert the constraints in $\Phi$ to a system of equations $\widetilde{\Phi}$ over $Q$ . Since $\Phi$ is satisfiable, the system $\widetilde{\Phi}$ is satisfiable as well. Hence, when $Q$ is abelian, we can find a satisfying assignment to $\widetilde{\Phi}$ in polynomial time using Gaussian elimination. Given such an assignment, we set each $x_{i}$ to be a uniformly random element from the corresponding coset in $G$ . For every constraint, the resulting sum is uniformly distributed over the appropriate coset of $H$ , and hence the constraint is satisfied with probability $|S|/|H|$ . One natural first choice is to take $H=\operatorname{cl}(S)$ , the subgroup generated by $S$ , but this choice is not always optimal. For instance, when $G=\mathbb{Z}_{4}\times\mathbb{Z}_{4}$ and $S=\{(0,1),(1,0)\}$ , the subgroup $\operatorname{cl}(S)$ is all of $G$ , whereas $S$ is contained in a coset of a smaller subgroup, giving a better approximation ratio. Therefore, the right choice is the smallest subgroup $H$ such that $S$ is contained in a coset of $H$ . For non-abelian groups, we additionally require $H$ to be normal and to contain the commutator subgroup $[G,G]$ , so that the quotient $G/H$ is abelian. This leads to the following theorem.

Theorem 2.

Fix any finite group $G$ and $S\subseteq G$ . Let $H_{S}$ is the smallest normal subgroup such that

1.

$[G,G]\subseteq H_{S}$ .
2.

$S\subseteq gH_{S}$ for some $g\in G$ , i.e., $S$ is a subset of some coset of $H_{S}$ .

then the problem $\text{Max-E$k$-LIN}_{S}(G)$ is approximable within a factor of $\frac{|S|}{|H_{S}|}$ on satisfiable instances. Furthermore, if $S^{-1}S$ generates $H_{S}$ , assuming $\mathbf{P}\neq\mathbf{NP}$ , for every $\varepsilon>0$ , it is $\mathbf{NP}$ -hard to approximate $\text{Max-E$k$-LIN}_{S}(G)$ within a factor of $\frac{|S|}{|H_{S}|}+\varepsilon$ .

Note that for any abelian group $G$ , the subgroup $[G,G]$ consists only of the identity element of $G$ . For non-abelian groups, the condition $[G,G]\subseteq H_{S}$ guarantees that the quotient group $Q:=G/H_{S}$ is abelian, which was crucial for the above-discussed approximation algorithm. See Theorem 13 for a straightforward generalization of the above approximation algorithm for non-abelian groups. The above theorem shows that even for abelian groups $G$ , the problem $\text{Max-E$k$-LIN}_{S}(G)$ is $\mathbf{NP}$ -hard on satisfiable instances, in general.

A predicate $P$ is called approximation resistant if it is $\mathbf{NP}$ -hard to do better than the random assignment algorithm. We are aware of two results, one by Håstad [25] on satisfying degree- $d$ equations over GF $[2]^{n}$ , and another by Bhangale-Khot [4] on Max-3LIN over non-abelian groups $G$ where $G$ is not a simple group. Both these predicates are approximation resistant in general (i.e., on almost satisfiable instances), but have non-trivial approximation algorithms on satisfiable instances. Thus, our result adds the generalized linear equation predicate to the small class of predicates that are known to be approximation resistant in general but have non-trivial approximation algorithms on satisfiable instances. We hope that our result gives another piece of information to help understand the approximability of Max-CSPs on satisfiable instances.

In Section 3, we give a simple $\frac{|S|}{|H_{S}|}$ -approximation algorithm for $\text{Max-E$k$-LIN}_{S}(G)$ for every finite group $G$ . The algorithm implicitly uses the abelian embedding of the generalized linearity predicate as defined in the series of work [6, 7, 8, 9] towards understanding the approximability of satisfiable CSPs. To show this optimal hardness result, we design a novel decoding procedure in the soundness analysis of the reduction, which may be of independent interest towards understanding the approximability of satisfiable CSPs.

1.1 Related Work

In this section, we go over relevant work on the inapproximability of Max-CSPs. The PCP Theorem [1, 2, 19] shows that Max- $P$ -CSPs are $\mathbf{NP}$ -hard to approximate within a factor of $(1-\delta)$ for some constant $\delta>0$ if checking satisfiability of $P$ -CSP is $\mathbf{NP}$ -complete. Håstad in his seminal work [24] greatly improved the hardness of approximation results for a few CSPs. Notable examples of the CSPs from his work include Max- $3$ SAT and Max- $3$ LIN. For Max-CUT, which is a $2$ -ary CSP, Håstad showed that it is $\mathbf{NP}$ -hard to approximate within a factor of $\frac{16}{17}$ . Khot [29] formulated the Unique Games Conjecture (UGC), which is a conjecture on the hardness of the Label Cover instances (see Definition 4) restricted to the constraints being $1$ -to- $1$ . Samorodnitsky and Trevisan [35] showed that Boolean Max- $k$ CSP (with arbitrary $k$ -ary Boolean predicates) is $\mathbf{NP}$ -hard to approximate beyond $O(\frac{k}{2^{k}})$ assuming the UGC, matching the best algorithm up to a constant factor. Khot, Kindler, Mossel, and O’Donnell [30] showed that Max-CUT is $\mathbf{NP}$ -hard to approximate within a factor of $0.878$ assuming the UGC, which matches the approximation guarantee of the Goemans-Williamson [20] algorithm for Max-CUT.

Raghavendra [33] presented an elegant result that generalizes the above Max-CUT reduction and establishes, for any Max- $P$ -CSP instance, the $(c,s)$ -integrality gap of the basic Semidefinite programming relaxation implies finding an $s+\varepsilon$ satisfying assignment on $c-\varepsilon$ satisfiable instances is $\mathbf{NP}$ -hard assuming the UGC. This result fully characterizes the approximability of Max- $P$ -CSPs assuming the UGC on almost satisfiable instances. Furthermore, given a fixed predicate $P$ , Raghavendra’s result does not explicitly give the optimal hardness factor for Max- $P$ -CSP. Austrin and Mossel [3] gave the right threshold for predicates that support a uniform and pairwise independent distribution. A distribution $\mu$ on $P^{-1}(1)\subseteq\Sigma^{k}$ is said to be pairwise independent if for every distinct pair $i,j\in[k]$ , the marginal of $\mu$ restricted to the coordinates $(i,j)$ is uniform over $\Sigma^{2}$ . Austrin and Mossel showed that such predicates are approximation resistant on almost satisfiable instances, assuming the UGC.

Chan [12] established a general criterion for approximation resistance, resolving the NP-hardness of Max- $k$ -CSP up to a constant factor and assuming $\mathbf{P}\neq\mathbf{NP}$ . Specifically, he proved the hardness for Max-CSPs where the domain is an abelian group $G$ and the predicate $P^{-1}(1)\subseteq G^{k}$ is a subgroup that satisfies a condition analogous to that identified by Austrin and Mossel.

The question of finding the optimal approximation algorithm (even assuming certain conjectures, like $d$ -to- $1$ conjecture [29] or Rich $2$ -to- $1$ conjecture [10]) for satisfiable instances of Max- $P$ -CSPs is wide open. In a recent series of work, Bhangale, Khot, and Minzer [6, 7] defined a property of abelian embeddability of the predicate towards understanding the approximability of satisfiable CSPs. A predicate $P:\Sigma^{k}\rightarrow\{0,1\}$ is said to have an abelian embedding in an abelian group $G$ , if there are maps $\alpha_{i}:\Sigma\rightarrow G$ , not all constant, such that $\sum_{i}\alpha_{i}(a_{i})=0_{G}$ for every $(a_{1},a_{2},\ldots,a_{k})\in P^{-1}(1)$ . They gave an optimal dictatorship test for $3$ -ary predicates that have no abelian embedding. Very recently, for certain $3$ -ary predicates that have an abelian embedding, they gave an approximation algorithm [8, 9] for satisfiable instances that uses a combination of Gaussian elimination as well as the SDP rounding algorithm. They also showed the “optimality” of this algorithm by giving a dictatorship test with matching parameters.

1.2 Techniques

In this section, we give an overview of the techniques in the inapproximability results of our main theorem.

1.2.1 Abelian Groups

We begin with the case of abelian groups to highlight one of the main differences in the analysis of the reduction compared to the seminal work of Håstad on Max-3LIN over an abelian group. We assume some familiarity with the Fourier analysis of functions over abelian groups (for instance, Chapter 8 of Ryan O’Donnell’s book [32]). Throughout the section, $\varepsilon>0$ is an arbitrarily small constant.

Starting with a work of Håstad [24], a typical way to prove the hardness of approximation is to start with an $\mathbf{NP}$ -hard problem called the Label Cover [22, 27, 28, 14, 31, 26, 23]. A gadget is built on top of the Label Cover instance to create an instance of a given CSP. For simplicity of the presentation, we focus here is on the most important and technical component of the reduction. This component is the construction of dictatorship tests and analyzing the tests.

A function $f:[q]^{n}\rightarrow[q]$ is called a dictator function if $f(x_{1},x_{2},\ldots,x_{n})=x_{j}$ for some $j\in[n]$ . A dictatorship test for a predicate $P:[q]^{k}\rightarrow\{0,1\}$ consists of a distribution $\mu$ that is (almost) supported on the set of satisfying assignments of $P$ . The test samples $k$ inputs $z_{1},z_{2},\ldots,z_{k}$ as follows: For each coordinate $i\in[n]$ , the tuple $((z_{1})_{i},(z_{2})_{i},\ldots,(z_{k})_{i})$ is sampled independently from $\mu$ . The test accepts $f$ if $P(f(z_{1}),f(z_{2}),\ldots,f(z_{k}))$ evaluates to $1$ , i.e., $f(z_{1}),f(z_{2}),\ldots,f(z_{k})$ forms a satisfying assignment for $P$ . It is clear that if $f$ is a dictator function, then the test passes with probability (almost) $1$ . This is because, in this case, we are checking if the $i^{th}$ coordinate of the inputs is from $P^{-1}(1)$ , which is always true by construction.

Once the distribution is fixed, the next step is to analyze the soundness of the dictatorship test, i.e., the probability with which the test passes if $f$ is “far from the dictator functions”. The notion of far from dictator functions changes based on the hardness reduction. A typical notion that is used is that the function has all the variables with degree $d=O(1)$ influences low. The influence of the $i^{th}$ coordinate on the function is the probability that, on a random input, changing the $i^{th}$ coordinate changes the values of the function. In terms of the Fourier coefficients of $f$ , this is equal to the following quantity:

\mathrm{Inf}_{i}(f):=\sum_{\alpha:\alpha_{i}\neq 0}|\hat{f}(\alpha)|^{2}.

Thus, the $i^{th}$ dictator function has $\mathrm{Inf}_{i}(f)=1$ . A degree- $d$ influence of the $i^{th}$ variable is given by the following expression,

\mathrm{Inf}_{i}^{\leqslant d}(f):=\sum_{\alpha:\alpha_{i}\neq 0\wedge|\alpha|% \leqslant d}|\hat{f}(\alpha)|^{2},

where $|\alpha|$ is the number of non-zero coordinates of $\alpha$ . With this notion of far from dictator functions in mind, the dictatorship test used in the hardness reduction [24] of Max-3LIN works as follows.

1.

Select $\boldsymbol{x},\boldsymbol{y}\sim G^{n}$ uniformly at random.
2.

Set $\boldsymbol{z}=\boldsymbol{x}+\boldsymbol{y}$ .
3.

For each $i\in[n]$ , resample $(x_{i},y_{i},z_{i})$ from $G^{3}$ uniformly at random, with probability $\varepsilon$ .
4.

Check if $f(\boldsymbol{x})+f(\boldsymbol{y})=f(\boldsymbol{z})$ .

It is clear that any dictator function passes the above test with probability at least $1-\varepsilon$ . To analyze the soundness of the test, we can express the test passing probability as follows:

\displaystyle\Pr[\mbox{Test passes}]=\frac{1}{|G|}\mathop{\mathbb{E}}_{(% \boldsymbol{x},\boldsymbol{y},\boldsymbol{z})}\left[\sum_{\chi_{\rho}\in\hat{G% }}\chi_{\rho}(f(\boldsymbol{x})+f(\boldsymbol{y})+f(\boldsymbol{z}))\right],

where the summation is over all the characters of the group $G$ . The term with $\chi_{\rho}$ being the trivial character gives $\frac{1}{|G|}$ . For the remaining terms with $\chi_{\rho}$ being a non-trivial character, we are left with analyzing the following expectation

\mathop{\mathbb{E}}_{(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})}\left[\chi% _{\rho}(f(\boldsymbol{x})+f(\boldsymbol{y})+f(\boldsymbol{z}))\right]=\mathop{% \mathbb{E}}_{(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})}\left[\chi_{\rho}(% f(\boldsymbol{x}))\cdot\chi_{\rho}(f(\boldsymbol{y}))\cdot\chi_{\rho}(f(% \boldsymbol{z}))\right].

By letting $F(\boldsymbol{w})=\chi_{\rho}(f(\boldsymbol{w}))$ and expanding the function $F$ with the Fourier basis over $G^{n}$ , and doing some simplifications, we get that the above expectation is upper bounded as follows.

	$\displaystyle\mathop{\mathbb{E}}_{(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z% })}\left[\chi_{\rho}(f(\boldsymbol{x}))\cdot\chi_{\rho}(f(\boldsymbol{y}))% \cdot\chi_{\rho}(f(\boldsymbol{z}))\right]\leqslant\sum_{\alpha}\|\hat{F}(% \alpha)\|^{3}\cdot(1-\varepsilon)^{\|\alpha\|}$
	$\displaystyle=\sum_{\alpha\wedge\|\alpha\|\leqslant d}\|\hat{F}(\alpha)\|^{3}\cdot% (1-\varepsilon)^{\|\alpha\|}+\sum_{\alpha\wedge\|\alpha\|>d}\|\hat{F}(\alpha)\|^{3}% \cdot(1-\varepsilon)^{\|\alpha\|}.$

Decoding Strategy

Now, because of the ‘noise’ (i.e., step 3 in the test), the second term can be shown to be negligible for some large $d$ as a function of $\varepsilon$ , by a simple application of Cauchy-Schwarz inequality and using Parseval’s identity. As for the first term, if it is non-negligible, then the structure of the function can be used in the hardness reduction starting from the Label Cover instance.

More precisely, the starting point of the reduction is a Label Cover instance (see Definition 4). It is $\mathbf{NP}$ -hard to distinguish between the Label Cover instances with value $1$ from instances with value at most $\delta$ for small $\delta>0$ . In the reduction, each vertex $v$ of the Label Cover instance is replaced with a cloud of vertices $C[v]$ where $|C[v]|$ is $G^{M}$ where $M$ is the label size of the vertex. These constitute the variables/literals of the reduced instance of Max-3LIN. The distribution on the constraints is specified by the above dictatorship test. If the value of the Label Cover instance is $1$ , then the value of the reduced Max-3LIN instance is at least $1-\varepsilon$ . Now, similar to the above analysis, if we fix an assignment $f$ to the Max-3LIN instance with value $\frac{1}{|G|}+\varepsilon$ for some $\varepsilon>0$ , then the assignment restricted to most of $C[v]$ , call it $f_{v}$ , has high degree- $d$ influential variables. From this, one can come up with a labeling to the Label Cover instance with value greater than $\delta=\delta(\varepsilon)$ , thereby showing the soundness of the reduction. The strategy simply picks a random non-trivial character $\rho$ , a Fourier coefficient $\widehat{\chi_{\rho}(f_{v})}(\alpha)$ of $f_{v}$ with probability $|\widehat{\chi_{\rho}(f_{v})}(\alpha)|^{2}$ and assign a label $i$ such that $\alpha_{i}$ is not a trivial character.

We now give the natural extension of the above dictatorship test to the generalized linear equation predicate that we consider in this paper. Towards this, fix an abelian group $(G,+)$ and a subset $S\subseteq G$ . Consider the following dictatorship test.

1.

Select $\boldsymbol{x},\boldsymbol{y}\sim G^{n}$ uniformly at random.
2.

Select $\boldsymbol{w}\sim S^{n}$ uniformly at random.
3.

Set $\boldsymbol{z}=-\boldsymbol{x}-\boldsymbol{y}+\boldsymbol{w}$ .
4.

Check if $f(\boldsymbol{x})+f(\boldsymbol{y})+f(\boldsymbol{z})\in S$ .

It is clear that every dictator function passes the test with probability $1$ . Similar to the above analysis, the soundness of the test can be expressed as follows:

\displaystyle\Pr[\mbox{Test passes}]=\frac{1}{|G|}\mathop{\mathbb{E}}_{(% \boldsymbol{x},\boldsymbol{y},\boldsymbol{z})}\left[\sum_{s\in S}\sum_{\chi_{% \rho}\in\hat{G}}\chi_{\rho}(f(\boldsymbol{x})+f(\boldsymbol{y})+f(\boldsymbol{% z})-s)\right],

Once again, the terms that correspond to the trivial character give $\frac{|S|}{|G|}$ (which corresponds to the approximation ratio of the algorithm that picks a random assignment). Note that our goal is to show that the test passes with probability almost $\frac{|S|}{|H_{S}|}+\varepsilon$ in the soundness towards proving Theorem 2. Once again, the term that corresponds to a given $s\in S$ and a character $\chi_{\rho}$ gives,

\mathop{\mathbb{E}}_{(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})}\left[\chi% _{\rho}(f(\boldsymbol{x})+f(\boldsymbol{y})+f(\boldsymbol{z})-s)\right]=% \mathop{\mathbb{E}}_{(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})}\left[\chi% _{\rho}(f(\boldsymbol{x}))\cdot\chi_{\rho}(f(\boldsymbol{y}))\cdot\chi_{\rho}(% f(\boldsymbol{z}))\cdot\chi_{\rho}(s)\right].

Ignoring the constant shift $\chi_{\rho}(s)$ , we are again left with analyzing the expectation

\mathop{\mathbb{E}}_{(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z})}\left[\chi% _{\rho}(f(\boldsymbol{x}))\cdot\chi_{\rho}(f(\boldsymbol{y}))\cdot\chi_{\rho}(% f(\boldsymbol{z}))\right].

Recall that the subgroup $H_{S}$ is the smallest subgroup such that $S\subseteq g+H_{S}$ for some $g\in G$ . Now, unlike the Max-3LIN, we cannot expect this expectation to be small when the functions $F$ have negligible degree- $d$ influences for some $d=O(1)$ . To see this, consider a character $\chi_{\rho}$ that is constant on the subgroup $H_{S}$ . If we let $f(\boldsymbol{x})=\sum_{i}x_{i}$ where the sum is the group operation, then the derived function $F$ has all degree- $d$ influences $0$ . However, the expectation becomes $\mathop{\mathbb{E}}[\chi_{\rho}(\sum_{i}w_{i})]$ , since $S\subseteq g+H_{S}$ for some $g$ , we get that the $\sum_{i}w_{i}\in ng+H_{S}$ , i.e, it always belongs to a fixed coset of $H_{S}$ . Since the character $\chi_{\rho}$ is constant on the subgroup $H_{S}$ (and hence constant on every coset of $H_{S}$ ), we get that the expectation is $1$ in absolute value. The number of such characters (including the trivial character) for which we cannot bound the expectation is precisely $|G|/|H_{S}|$ . This gives the right factor $\frac{|S|}{|H_{S}|}$ in the test passing probability that we need for our Theorem 2.

Now, consider the character $\chi_{\rho}$ , which is not constant on $H_{S}$ . Similar to Håstad’s analysis, we can upper bound the corresponding expectation as follows

\displaystyle\mathop{\mathbb{E}}_{(\boldsymbol{x},\boldsymbol{y},\boldsymbol{z% })}\left[\chi_{\rho}(f(\boldsymbol{x}))\cdot\chi_{\rho}(f(\boldsymbol{y}))% \cdot\chi_{\rho}(f(\boldsymbol{z}))\right]

\displaystyle\leqslant\sum_{\alpha}|\hat{F}(\alpha)|^{3}\cdot(1-\eta)^{|\alpha% |_{S}},

where $\eta>0$ is a non-zero constant that only depends on $|G|$ and $|\alpha|_{S}$ is the number of coordinates of $\alpha$ where the character $\alpha_{i}$ is not constant on the subgroup $H_{S}$ . In order to work with this expression, we modify the notion of far from dictator functions that will be useful for our hardness reduction as follows.

Modified low-degree influences

A modified degree- $d$ influence of the $i^{th}$ variable is expressed as the following expression,

\mathrm{Inf}_{i}^{\leqslant d}(f):=\sum_{\alpha:\alpha_{i}\neq 0\wedge|\alpha|% _{S}\leqslant d}|\hat{f}(\alpha)|^{2},

where $|\alpha|_{S}$ is the number of coordinates of $\alpha$ where the character $\alpha_{i}$ is not constant on the subgroup $H_{S}$ . With this change, we split the summation as follows:

\displaystyle\sum_{\alpha}|\hat{F}(\alpha)|^{3}\cdot(1-\eta)^{|\alpha|_{S}}

\displaystyle=\sum_{\alpha\wedge|\alpha|_{S}\leqslant d}|\hat{F}(\alpha)|^{3}% \cdot(1-\eta)^{|\alpha|_{S}}+\sum_{\alpha\wedge|\alpha|_{S}>d}|\hat{F}(\alpha)% |^{3}\cdot(1-\eta)^{|\alpha|_{S}}.

Again, the second term is negligible for some large $d=O_{|G|}(1)$ .

Modified Decoding Strategy

In our analysis of the reduction, we need to show that the terms that are similar to the first term are not negligible, then there is a decoding strategy (similar to the one described in the reduction to Max-3LIN above) in the hardness reduction starting from the Label Cover instance. The following strategy works. The modified strategy picks a random non-trivial irreducible representation $\rho$ that is not constant on $H_{S}$ , a Fourier coefficient $\widehat{\chi_{\rho}(f_{v})}(\alpha)$ of $f_{v}$ with probability $|\widehat{\chi_{\rho}(f_{v})}(\alpha)|^{2}$ and assign a label $i$ such that the character corresponding to $\alpha_{i}$ is not constant on $H_{S}$ .

1.2.2 Non-abelian Groups

The above dictatorship test can be easily modified for the non-abelian case in a natural way

1.

Select $\boldsymbol{x},\boldsymbol{y}\sim G^{n}$ uniformly at random.
2.

Select $\boldsymbol{s}\in S^{n}$ uniformly at random.
3.

For each $i\in[n]$ , set $z_{i}=y_{i}^{-1}\text{ $\bullet$}\hskip 2.0ptx_{i}^{-1}\text{ $\bullet$}\hskip 2% .0pts_{i}$ .
4.

Check if $f(\boldsymbol{x})\text{ $\bullet$}\hskip 2.0ptf(\boldsymbol{y})\text{ $\bullet% $}\hskip 2.0ptf(\boldsymbol{z})\in S$ .

The completeness case is trivial. In the soundness case, we again express the test passing probability as

\displaystyle\Pr[\mbox{Test passes}]=\frac{1}{|G|}\mathop{\mathbb{E}}_{(% \boldsymbol{x},\boldsymbol{y},\boldsymbol{z})}\left[\sum_{s\in S}\left[\sum_{% \rho\in\mathsf{Irrep}(G)}\dim(\rho)\cdot\chi_{\rho}(f(\boldsymbol{x})\text{ $% \bullet$}\hskip 2.0ptf(\boldsymbol{y})\text{ $\bullet$}\hskip 2.0ptf(% \boldsymbol{z})\text{ $\bullet$}\hskip 2.0pts^{-1})\right]\right],

where the inner sum is over all irreducible representations of $(G,\text{ $\bullet$}\hskip 2.0pt)$ and $\dim(\rho)$ is the dimension of the representation $\rho$ . Similarly to the abelian case, for certain representations of dimension $1$ (that are constant on the subgroup $H_{S}$ defined in Theorem 2), we bound the expectation by $1$ in absolute value. This gives the factor $\frac{|S|}{|H_{S}|}$ . The analysis for the remaining dimension $1$ representations, Lemma 16, is analogous to the one described in the abelian case but focuses on the natural structure of non-abelian groups and generalized linear equation predicates. For some technical reasons, for non-abelian groups, we could analyze this under the assumption that $S^{-1}S$ generates the subgroup $H_{S}$ .

Regarding representations with dimension $\geqslant 2$ , we treat the analysis of Bhangale and Khot [4] as a black box (Lemma 19) to conclude that the associated expectations are small unless they yield a decoding strategy for the Label Cover instance. For some technical reasons, the analysis of this part of the reduction requires the use of Layered Label Cover instead of the bipartite Label Cover. Therefore, in our main reduction, we also use a Layered Label Cover instance as a starting point, but we only use the layered version in the proof of Lemma 19 to adopt results from [5]. For the primary part of this paper, we only need a bipartite Label Cover instance.

$\blacktriangleright$ Remark 3.

The conference version of the paper [4] had an error, which the authors fixed with the use of Layered Label Cover as a starting point.⁴⁴4personal communication [5] This fix is reflected in the Lemma 19 [5, Claim 4.5] that we use as black-box.

1.3 Organization

We begin Section 2 by defining the Label Cover instance and the hardness of approximation of Label Cover, which is the starting point of our reduction. In Section 2.2, we go over the basics of Fourier analysis over general finite groups. We formally give the approximation algorithm described in the introduction in Section 3. Finally, in Section 4 we give our hardness reduction for $\text{Max-E$3$-LIN}_{S}(G)$ and analyze the reduction. The hardness for $\text{Max-E$k$-LIN}_{S}(G)$ for $k\geqslant 4$ follows easily from a similar reduction, thereby proving the main Theorem 2.

2 Preliminaries

2.1 Label Cover

We start by defining the Label Cover and Layered Label Cover problem, which we use as a starting point for our reduction.

Definition 4 (Label Cover).

An instance $\Psi=(U,V,E,[L],[R],\{\pi_{e}\}_{e\in E})$ of the Label Cover constraint satisfaction problem consists of a bi-regular bipartite graph $(U,V,E)$ , alphabets $[L]$ and $[R]$ and a surjective projection map $\pi_{e}:[L]\rightarrow[R]$ for every edge $e\in E$ . Given a labeling $\ell:U\rightarrow[L],\ell:V\rightarrow[R]$ , an edge $e=(u,v)$ is said to be satisfied by $\ell$ if $\pi_{e}(\ell(u))=\ell(v)$ .

$\Psi$ is said to be satisfiable if there exists a labeling that satisfies all the edges. $\Psi$ is said to be at most $\delta$ -satisfiable if every labeling satisfies at most a $\delta$ fraction of the edges.

The hardness of Label Cover stated below follows from the PCP Theorem [2, 1, 19] and Raz’s Parallel Repetition Theorem [34].

Theorem 5 (Hardness of Label Cover).

For every $r\in\mathbb{N}$ , there is a deterministic $n^{O(r)}$ -time reduction from a 3-SAT instance of size $n$ to an instance $\Psi=(U,V,E,[L],[R],\{\pi_{e}\}_{e\in E})$ of Label Cover with the following properties: $|U|,|V|\leqslant n^{O(r)}$ ; $L,R\leqslant 2^{O(r)}$ ; $\Psi$ is bi-regular with degrees bounded by $2^{O(r)}$ .

YES Case: If the 3-SAT instance is satisfiable, then $\Psi$ is satisfiable.
NO Case: If the 3-SAT instance is unsatisfiable, then $\Psi$ is at most $2^{-r}$ satisfiable

For our hardness result, we need the following variant of the Label Cover problem.

Definition 6 (Layered Label Cover).

An $T$ -Layered Label Cover instance, given by $\mathcal{H}=(\mathcal{V}=\{V_{1},\dots,V_{T}\},\{\Pi_{i,j}\}_{1\leqslant i<j% \leqslant T}\},\{[R_{i}]_{i\in[T]}\}$ consist of $T$ sets of vertices $\mathcal{V}=\{V_{1},\dots,V_{T}\}$ . The label set of vertices in layer $i$ is denoted by $[R_{i}]$ . Every pair of layers $1\leq i<j\leq l$ has a set of constraints $\Pi_{i,j}$ between the vertices in $V_{i}$ and $V_{j}$ . The constraint between $v\in V_{i}$ and $u\in V_{j}$ (if it exists in $\Pi_{i,j}$ ) is denoted by $\pi_{vu}$ . Moreover, every constraint between a pair of vertices is a projection constraint: for every assignment $k\in[R_{i}]$ to $v\in V_{i}$ , there is a unique assignment to $u\in V_{j}$ that satisfies the constraint $\pi_{vu}$ .

Theorem 7 ([15], Hardness of Layered Label Cover).

For any constant parameters $T\geq 2$ , $r\in\mathbb{Z}$ , the following problem is NP-hard. Given an $T$ -Layered Label Cover instance $\mathcal{H}=(\mathcal{V}=\{V_{1},...,V_{T}\},\{\Pi_{i,j}\}_{1\leq i<j\leq T},% \{[R_{t}]\}_{t\in[T]})$ where all variable ranges $R_{t}$ are of size $2^{O(Tr)}$ , distinguish between the following two cases:

Completeness.: There is an assignment satisfying all the constraints of the Label Cover instance. In this case, we say that $\mathcal{H}$ is fully satisfiable.
Soundness.: For every $1\leq i<j\leq T$ , no assignment satisfies more than a $2^{-r}$ fraction of the set of constraints $\Pi_{i,j}$ between layers $i$ and $j$ . In this case, we say that $\mathcal{H}$ is at most $2^{-r}$ -satisfiable.

2.2 Fourier analysis over non-abelian group

We assume familiarity with the representation theory and Fourier analysis of functions over finite non-abelian groups. We refer the reader to the book by Terras [37] and the work of Bhangale and Khot [4] for standard definitions (such as irreducible representations, characters, Plancherel’s, and Parseval’s identity) which we omit here for brevity.

In this paper, we only consider non-abelian groups that are finite. Let $G=(G,\text{ $\bullet$}\hskip 2.0pt)$ be a finite non-abelian group. The identity element of a group is denoted by $1_{G}$ . We assume familiarity with basic definitions of representations, dimensions, invariant subspaces, and tensor products. We will denote the set of all irreducible representations of $G$ up to isomorphism by $\mathsf{Irrep}(G)$ .

Fact 8.

Let $G$ be a group and $H$ be any subgroup of $G$ . If $\rho\in\mathsf{Irrep}(G)$ then $\rho$ restricted to $H$ is also a (not necessarily irreducible) representation of $H$ .

The following proposition shows that matrix entries of irreducible representations are “orthogonal” with respect to a symmetric bilinear form, unless they are conjugates of each other, in which case the corresponding product is the inverse of the dimension of the representation.

Proposition 9.

If $\rho$ and $\tau$ are two non-isomorphic irreducible representations of $G$ then for any $i, j, k, l$ we have

\langle(\rho)_{ij}\mid(\tau)_{kl}\rangle_{G}=0,

(2)

where $\langle f_{1}\mid f_{2}\rangle_{G}:=\frac{1}{|G|}\sum_{g\in G}f_{1}(g)f_{2}(g^% {-1})$ (called a “symmetric bilinear form”). Also,

\langle(\rho)_{ij}\mid(\rho)_{kl}\rangle_{G}=\frac{\delta_{il}\delta_{jk}}{% \dim(\rho)},

(3)

where $\delta_{ij}$ is the delta-function which is $1$ if $i=j$ and $0$ otherwise.

We use Proposition 9 many times in the proof. For convenience, we note an important identity that follows from Proposition 9 (by setting $\tau$ to be the trivial map $\{\mathbf{1}\}$ ).

Proposition 10.

If $\rho\in\mathsf{Irrep}(G)\hskip-3.0pt\setminus\hskip-3.0pt\{\mathbf{1}\}$ , $\sum_{g\in G}\rho(g)=0$ .

In this paper, we will be interested in studying $L^{2}(G)$ , the space of functions from a finite group $G$ to the complex numbers $\mathbb{C}$ . Define the inner product $\langle\cdot,\cdot\rangle_{L^{2}(G)}$ on $L^{2}(G)$ by $\langle f,g\rangle_{L^{2}(G)}=\mathop{\mathbb{E}}_{x\in G}[f(x)\overline{g(x)}]$ . The character of a representation $\rho$ is the function $\chi_{\rho}:G\rightarrow\mathbb{C}$ defined by $\chi_{\rho}(g)=\mathsf{tr}(\rho(g))$ .

We will use the following propositions.

Proposition 11 (Orthogonality of characters).

For $\rho,\tau\in\mathsf{Irrep}(G)$ , we have

\frac{1}{|G|}\sum_{g\in G}\chi_{\rho}(g)\overline{\chi_{\tau}(g)}=\begin{cases% }1\quad\rho_{V}\cong\tau_{V},\\ 0\quad otherwise.\end{cases}

This proposition also shows that the maximum dimension of any irreducible representation of $G$ is at most $\sqrt{G}$ .

Proposition 12.

\sum\limits_{\rho\in\mathsf{Irrep}(G)}\dim(\rho)\chi_{\rho}(g)=\begin{cases}|G% |\quad g=1_{G},\\ 0\quad otherwise.\end{cases}

This implies $\sum_{\rho\in\mathsf{Irrep}(G)}\dim(\rho)^{2}=|G|.$

3 An Approximation Algorithm

In this section, we give an approximation algorithm for $\text{Max-E$3$-LIN}_{S}(G)$ for any group $(G,\text{ $\bullet$}\hskip 2.0pt)$ and $S\subseteq G$ . This algorithm is a straightforward generalization of the algorithm for abelian groups $G$ discussed in the introduction. We repeat it here for completeness.

Theorem 13.

There exists a $\frac{|S|}{|H_{S}|}$ -approximation algorithm for $\text{Max-E$3$-LIN}_{S}(G)$ , where $H_{S}$ is the smallest normal subgroup such that (i) $[G,G]\subseteq H_{S}$ , and (ii) $S$ is a subset of some coset of $H_{S}$ .

Proof.

Let $\Phi$ be an instance of $\text{Max-E$3$-LIN}_{S}(G)$ with constraints $(C_{1},C_{2},\ldots,C_{m})$ over the variables $X=\{x_{1},x_{2},\ldots,x_{n}\}$ . We first convert the set of constraints to a system of equations, denoted by $\tilde{\Phi}$ , over the group $(Q,+):=G/H_{S}$ with variables $Y=\{y_{1},y_{2},\ldots,y_{n}\}$ . Note that $H_{S}$ is a normal subgroup of $G$ containing the commutator subgroup such that $S\subseteq gH_{S}$ for some $g\in G$ . Thus, $Q$ is an abelian group.

Consider a constraint $C_{i}$ which is of the form $(a_{i_{1}}\text{ $\bullet$}\hskip 2.0ptx_{i_{1}})\text{ $\bullet$}\hskip 2.0pt% (a_{i_{2}}\text{ $\bullet$}\hskip 2.0ptx_{i_{2}})\text{ $\bullet$}\hskip 2.0pt% (a_{i_{3}}\text{ $\bullet$}\hskip 2.0ptx_{i_{3}})\in S$ . We convert this to the equation over $Q$ as

[a_{i_{1}}]_{Q}+y_{i_{1}}+[a_{i_{2}}]_{Q}+y_{i_{2}}+[a_{i_{3}}]_{Q}+y_{i_{3}}=% [S]_{Q},

where $[S]_{Q}$ is an element of $Q$ that corresponds to the coset of $H_{S}$ containing $S$ , and the element $[g]_{Q}$ corresponds to the coset of $H_{S}$ containing $g$ .

As $\Phi$ is satisfiable, consider the satisfying assignment $\boldsymbol{\alpha}:X\rightarrow G$ to $\Phi$ . Consider the assignment $\tilde{\boldsymbol{\alpha}}:Y\rightarrow Q$ given by the natural map $\tilde{\boldsymbol{\alpha}}(y_{i})=[\boldsymbol{\alpha}(x_{i})]_{Q}$ . It is easy to see that $\tilde{\boldsymbol{\alpha}}$ satisfies all the equations from the instance $\tilde{\Phi}$ , and hence, $\tilde{\Phi}$ is satisfiable.

Since $\tilde{\Phi}$ is a system of equations over an abelian group $(Q,+)$ , we can find a satisfying assignment to $\tilde{\Phi}$ in polynomial time using Gaussian elimination [21]. Let $\tilde{\boldsymbol{\beta}}$ be the assignment returned by this procedure. To construct the final assignment to the $X$ variables, we simply set $x_{i}$ to be a random element from the coset $\tilde{\boldsymbol{\beta}}(y_{i})$ . Let $\boldsymbol{\beta}:X\rightarrow G$ be the random assignment given by the above procedure. It can be easily observed that $\boldsymbol{\beta}$ satisfies a given constraint $C_{i}$ in $\Phi$ with probability $\frac{|S|}{|H_{S}|}$ and hence $\boldsymbol{\beta}$ satisfies $\frac{|S|}{|H_{S}|}$ fraction of the constraints in expectation. The randomized algorithm can be easily derandomized using the method of conditional expectations. $\hfill\blacktriangleleft$

4 Hardness of $\text{Max-E$3$-LIN}_{S}(G)$

We start with some basic facts. For a nonabelian group $G$ , the quotient group $G/[G,G]$ is an abelian group. The dual of $G/[G,G]$ is isomorphic to

\{\chi_{\rho}\nobreak\ |\nobreak\ \rho\in\mathsf{Irrep}(G),\dim(\rho)=1\}

We denote this subgroup of $\hat{G}$ as $\widehat{G/[G,G]}$ .

Similarly, consider any normal subgroup $H\trianglelefteq G$ such that $[G,G]\subseteq H$ , the quotient group $G/H$ is an abelian group that is isomorphic to a subgroup of $G/[G,G]$ . Furthermore, the dual of $G/H$ is isomorphic to

\{\chi_{\rho}\nobreak\ |\nobreak\ \rho\in\mathsf{Irrep}(G),\dim(\rho)=1,\chi_{% \rho}(h)=1,\forall h\in H\}.

Main Reduction

We now give a reduction from a Layered Label Cover instance, denoted by, $\mathcal{H}=(\mathcal{V}=\{V_{1},\dots,V_{T}\},\{\Pi_{i,j}\}_{1\leqslant t<t^{% \prime}\leqslant T}\},\{[R_{t}]_{t\in[T]}\}$ to a $\text{Max-E$3$-LIN}_{S}(G)$ instance $\Phi$ over a non-abelian group $G$ . For $\delta>0$ , we will use the following setting of $T$ and $r$ in Theorem 7

2^{-r}\leqslant\min\left\{\frac{\delta^{10}}{(2|G|)^{20}},\frac{\delta^{2}}{10% |G|^{10K}}\right\},\quad T\geqslant\left(\frac{8|G|^{3}}{\delta}\right)^{4},

where $K:=\frac{8|G|^{6}}{\delta^{2}}$ .

Consider the Layered Label Cover instance $\mathcal{H}$ . For all $t\in[T]$ and for each $v\in V_{t}$ , we create a cluster $C[v]$ of literals of size $|G|^{R_{t}}$ . In each cluster $C[v]$ , each literal is indexed by a string of length $R_{t}$ . For any string $(1_{G},\boldsymbol{y})\in G^{R_{t}}$ , its corresponding literals are $g\text{ $\bullet$}\hskip 2.0pt(1_{G},\boldsymbol{y})$ for $g\in G$ , where the string $g\text{ $\bullet$}\hskip 2.0pt(1_{G},\boldsymbol{y})$ is $(g,g\text{ $\bullet$}\hskip 2.0pty_{1},\ldots,g\text{ $\bullet$}\hskip 2.0pty_% {R_{t-1}})$ .

An assignment to the instance that we are going to create is given by the maps $A_{v}:G^{R_{t}}\rightarrow G$ for all $v\in V_{t}$ and all $t\in[T]$ . Note that any such assignment is assumed to be folded, i.e., $A_{v}(g\text{ $\bullet$}\hskip 2.0pt(1_{G},\boldsymbol{y}))=g\text{ $\bullet$}% \hskip 2.0ptA_{v}((1_{G},\boldsymbol{y}))$ .

The distribution on the constraint of the reduced instance $\Phi$ of $\text{Max-E$3$-LIN}_{S}(G)$ is given by the following PCP verifier.

1.

Pick a uniformly random pair $(t,t^{\prime})$ satisfying $1\leqslant t<t^{\prime}\leqslant T$ .
2.

Choose an edge constraint $\pi_{uv}:[R_{t}]\rightarrow[R_{t^{\prime}}]$ from $\mathcal{H}$ uniformly at random.
3.

Sample a string $\boldsymbol{x}\sim G^{R_{t^{\prime}}}$ and $\boldsymbol{y}\sim G^{R_{t}}$ independently and uniformly at random.
4.

Sample an element $\boldsymbol{s}\in S^{R_{t}}$ uniformly at random.
5.

For each $j\in[R_{t}]$ , set $z_{j}=y_{j}^{-1}\text{ $\bullet$}\hskip 2.0ptx_{\pi_{uv}(j)}^{-1}\text{ $% \bullet$}\hskip 2.0pts_{j}$ .
6.

Accept if and only if $A_{v}(\boldsymbol{x})\text{ $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{y})\text{ % $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{z})\in S$ .

4.1 Completeness

If $\mathcal{H}$ is fully satisfiable, then there exists a corresponding assignment $\sigma$ such that all the constraints are satisfiable. Let $A_{v}(\boldsymbol{x})=x_{\sigma(v)}$ and $A_{u}(\boldsymbol{y})=y_{\sigma(u)}$ , i.e., the dictator functions. Then, the test passes as,

	$\displaystyle A_{v}(\boldsymbol{x})\text{ $\bullet$}\hskip 2.0ptA_{u}(% \boldsymbol{y})\text{ $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{z})$
	$\displaystyle=x_{\sigma(v)}\text{ $\bullet$}\hskip 2.0pty_{\sigma(u)}\text{ $% \bullet$}\hskip 2.0ptz_{\sigma(u)}$
	$\displaystyle=x_{\sigma(v)}\text{ $\bullet$}\hskip 2.0pty_{\sigma(u)}\text{ $% \bullet$}\hskip 2.0pt(y_{\sigma(u)})^{-1}\text{ $\bullet$}\hskip 2.0pt(x_{\pi_% {u,v}(\sigma(u))})^{-1}\text{ $\bullet$}\hskip 2.0pts_{\sigma(u)}$
	$\displaystyle=x_{\sigma(v)}\text{ $\bullet$}\hskip 2.0pty_{\sigma(u)}\text{ $% \bullet$}\hskip 2.0pt(y_{\sigma(u)})^{-1}\text{ $\bullet$}\hskip 2.0pt(x_{% \sigma(v)})^{-1}\text{ $\bullet$}\hskip 2.0pts_{\sigma(u)}$		(Using $\pi_{u,v}(\sigma(u))=\sigma(v)$ )
	$\displaystyle=s_{\sigma(u)}\in S.$

Hence, the test always passes. Thus, the value of the instance $\Phi$ is $1$ .

4.2 Soundness

In this section, we prove the soundness of the analysis.

Lemma 14.

For every $\delta>0$ , if the Layered Label Cover instance $\mathcal{H}$ is at most $2^{-r}$ , then the $\text{Max-E$3$-LIN}_{S}(G)$ instance $\Phi$ is at most $\frac{|S|}{|H_{S}|}+\delta$ satisfiable.

Proof.

Fix the assignment $\{A_{v}\}_{v\in\mathcal{V}}$ to the instance $\Phi$ . We define the value of an assignment $A$ , $\textrm{value}(A)$ , as the probability that the above test passes. The following expression gives the value of this assignment $A$ ,

\displaystyle\mathop{\mathbb{E}}_{1\leqslant t<t^{\prime}\leqslant T}\left[% \mathop{\mathbb{E}}_{\begin{subarray}{c}\pi_{uv}\in\Pi_{t,t^{\prime}}\\ (\boldsymbol{x},\boldsymbol{y},\boldsymbol{s})\end{subarray}}\left[\sum_{s\in S% }\left[\frac{1}{|G|}\sum_{\rho\in\mathsf{Irrep}(G)}\dim(\rho)\cdot\chi_{\rho}(% A_{v}(\boldsymbol{x})\text{ $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{y})\text{ % $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{z})\text{ $\bullet$}\hskip 2.0pts^{-1}% )\right]\right]\right].

By Proposition 12, this expression equals $1$ if and only if $A_{v}(\boldsymbol{x})\text{ $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{y})\text{ % $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{z})\in S$ , and $0$ otherwise. We can rewrite this expression according to the representations $\rho\in\mathsf{Irrep}(G)$ ,

	$\displaystyle\mathrm{value}(A)$
	$\displaystyle=\frac{1}{\|G\|}\mathop{\mathbb{E}}_{1\leqslant t<t^{\prime}% \leqslant T}\left[\sum_{\rho\in\mathsf{Irrep}(G)}\sum_{s\in S}\mathop{\mathbb{% E}}_{\begin{subarray}{c}\pi_{uv}\in\Pi_{t,t^{\prime}}\\ \boldsymbol{x},\boldsymbol{y},\boldsymbol{s}\end{subarray}}\left[\dim(\rho)% \cdot\chi_{\rho}(A_{v}(\boldsymbol{x})\text{ $\bullet$}\hskip 2.0ptA_{u}(% \boldsymbol{y})\text{ $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{z})\text{ $% \bullet$}\hskip 2.0pts^{-1})\right]\right]$
	$\displaystyle=\frac{1}{\|G\|}\mathop{\mathbb{E}}_{1\leqslant t<t^{\prime}% \leqslant T}\left[\sum_{\begin{subarray}{c}\rho\in\widehat{G/H_{S}}\\ \dim(\rho)=1\end{subarray}}\sum_{s\in S}\mathop{\mathbb{E}}_{\begin{subarray}{% c}\pi_{uv}\in\Pi_{t,t^{\prime}}\\ \boldsymbol{x},\boldsymbol{y},\boldsymbol{s}\end{subarray}}\left[\dim(\rho)% \chi_{\rho}(A_{v}(\boldsymbol{x})\text{ $\bullet$}\hskip 2.0ptA_{u}(% \boldsymbol{y})\text{ $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{z})\text{ $% \bullet$}\hskip 2.0pts^{-1})\right]\right]$		(4)
	$\displaystyle+\frac{1}{\|G\|}\mathop{\mathbb{E}}_{1\leqslant t<t^{\prime}% \leqslant T}\left[\sum_{\begin{subarray}{c}\rho\notin\widehat{G/H_{S}}\\ \dim(\rho)=1\end{subarray}}\sum_{s\in S}\mathop{\mathbb{E}}_{\begin{subarray}{% c}\pi_{uv}\in\Pi_{t,t^{\prime}}\\ \boldsymbol{x},\boldsymbol{y},\boldsymbol{s}\end{subarray}}\left[\dim(\rho)% \chi_{\rho}(A_{v}(\boldsymbol{x})\text{ $\bullet$}\hskip 2.0ptA_{u}(% \boldsymbol{y})\text{ $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{z})\text{ $% \bullet$}\hskip 2.0pts^{-1})\right]\right]$		(5)
	$\displaystyle+\frac{1}{\|G\|}\mathop{\mathbb{E}}_{1\leqslant t<t^{\prime}% \leqslant T}\left[\sum_{\dim(\rho)\geqslant 2}\sum_{s\in S}\mathop{\mathbb{E}}% _{\begin{subarray}{c}\pi_{uv}\in\Pi_{t,t^{\prime}}\\ \boldsymbol{x},\boldsymbol{y},\boldsymbol{s}\end{subarray}}\left[\dim(\rho)% \cdot\chi_{\rho}(A_{v}(\boldsymbol{x})\text{ $\bullet$}\hskip 2.0ptA_{u}(% \boldsymbol{y})\text{ $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{z})\text{ $% \bullet$}\hskip 2.0pts^{-1})\right]\right].$		(6)

Term (4) is a constant between any two layers. As for term (5), we prove that they can be used to decode a valid assignment to any pair of layers unless they are negligible along a random path $p$ . Finally, for term (6), we use [5] as a black box and show they are negligible along a random path $p$ .

For term 4 and term 5, since they have $\dim(\rho)=1$ , the character $\chi_{\rho}$ is a homomorphism. Thus, we have

\displaystyle\dim(\rho)\chi_{\rho}(A_{v}(\boldsymbol{x})\text{ $\bullet$}% \hskip 2.0ptA_{u}(\boldsymbol{y})\text{ $\bullet$}\hskip 2.0ptA_{u}(% \boldsymbol{z})\text{ $\bullet$}\hskip 2.0pts^{-1})=\chi_{\rho}(A_{v}(% \boldsymbol{x})\text{ $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{y})\text{ $% \bullet$}\hskip 2.0ptA_{u}(\boldsymbol{z}))\cdot\chi_{\rho}(s^{-1}).

For term (4), as $\chi_{\rho}$ is a 1-bounded function, it’s upper bounded by

\displaystyle\frac{1}{|G|}\sum_{\begin{subarray}{c}\rho\in\widehat{G/H_{S}}\\ \dim(\rho)=1\end{subarray}}\sum_{s\in S}1=\frac{1}{|G|}|S|\left|\frac{G}{H_{S}% }\right|=\frac{|S|}{|H_{S}|}.

4.2.1 Bounding expressions in (5)

We now bound the term (5). Using $|\chi_{\rho}(s^{-1})|\leqslant 1$ , we have (5) is at most

\displaystyle\frac{|S|}{|G|}\sum_{\begin{subarray}{c}\rho\notin\widehat{G/H_{S% }}\\ \dim(\rho)=1\end{subarray}}\mathop{\mathbb{E}}_{\begin{subarray}{c}(u,v)\\ \boldsymbol{x},\boldsymbol{y},\boldsymbol{s}\end{subarray}}\left[\chi_{\rho}(A% _{v}(\boldsymbol{x}))\cdot\chi_{\rho}(A_{u}(\boldsymbol{y}))\cdot\chi_{\rho}(A% _{u}(\boldsymbol{z}))\right],

We argue that if this expression is large, then a decoding strategy exists for the Label Cover instance. We need the following simple lemma.

Lemma 15.

Let $h:G^{n}\rightarrow G$ be any folded function, $\beta$ is a representation of $G^{n}$ . Define $s(\beta):=\{i\nobreak\ |\nobreak\ \beta_{i}\notin\widehat{G/H_{S}}\}$ . Let $g(\boldsymbol{x})=\chi_{\rho}(h(\boldsymbol{x}))$ for $\chi_{\rho}\notin\widehat{G/H_{S}}$ and $\dim(\rho)=1$ , then $\hat{g}(\beta)=0$ for all $\beta$ with $s(\beta)=\emptyset$ .

Proof.

By definition, we have

	$\displaystyle\hat{g}(\beta)$	$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{x}\in G^{n}}[\chi_{\rho}(h(% \boldsymbol{x}))\beta(\boldsymbol{x})]$
		$\displaystyle=\mathop{\mathbb{E}}_{\begin{subarray}{c}\boldsymbol{y}\in G^{n-1% }\\ x_{1}=1_{G}\end{subarray}}\left[\mathop{\mathbb{E}}_{c\in G}[\chi_{\rho}(h(c% \text{ $\bullet$}\hskip 2.0pt(1_{G},\boldsymbol{y})))\beta(\boldsymbol{c}\text% { $\bullet$}\hskip 2.0pt(1_{G},\boldsymbol{y}))]\right]$
		$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{y}\in G^{n-1}}\left[\mathop{% \mathbb{E}}_{c\in G}[\chi_{\rho}(c)\cdot\chi_{\rho}(h((1_{G},\boldsymbol{y})))% \cdot\beta(\boldsymbol{c})\cdot\beta((1_{G},\boldsymbol{y}))]\right]$
		$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{y}\in G^{n-1}}\chi_{\rho}(h((1_% {G},\boldsymbol{y})))\beta((1_{G},\boldsymbol{y}))\cdot\mathop{\mathbb{E}}_{c% \in G}\left[\chi_{\rho}(c)\beta(\boldsymbol{c})\right].$

If $\beta$ satisfies $|s(\beta)|=0$ , then $\beta(\boldsymbol{c})=\bigotimes_{i=1}^{L}\beta_{i}(c)$ is a complex number. Therefore, there always exists a $\rho^{\prime}$ such that $\dim(\rho^{\prime})=1$ and $\chi_{\rho}(c)\beta(\boldsymbol{c})=\chi_{\rho^{\prime}}(c)$ . Furthermore, such $\rho^{\prime}\notin\widehat{G/H_{S}}$ since for any element $q\in G/H_{S}$ , $\beta(q)=1$ and $\chi_{\rho}(q)\neq 1$ , indicating that $\chi_{\rho^{\prime}}(q)\neq 1$ . Hence, by Proposition 10,

\displaystyle\hat{g}(\beta)=\mathop{\mathbb{E}}_{\boldsymbol{y}\in G^{n-1}}% \chi_{\rho}(h((1_{G},\boldsymbol{y})))\beta((1_{G},\boldsymbol{y}))\cdot% \mathop{\mathbb{E}}_{c\in G}[\chi_{\rho^{\prime}}(c)]=0.

$\hfill\blacktriangleleft$

We now prove the following main lemma from this section.

Lemma 16.

If the Layered Label Cover instance $\mathcal{H}$ is at most $2^{-r}$ satisfiable, then for any $\dim(\rho)=1$ such that $\rho\notin\widehat{G/H_{S}}$ ,

\displaystyle\left|\mathop{\mathbb{E}}_{1\leqslant t<t^{\prime}\leqslant T}% \left[\mathop{\mathbb{E}}_{\pi_{uv}\in\Pi_{t,t^{\prime}}}\left[\mathop{\mathbb% {E}}_{\boldsymbol{x},\boldsymbol{y}}\left[\chi_{\rho}(A_{v}(\boldsymbol{x}))% \cdot\chi_{\rho}(A_{u}(\boldsymbol{y}))\cdot\chi_{\rho}(A_{u}(\boldsymbol{z}))% \right]\right]\right]\right|\leqslant\frac{\delta}{2|G|},

(7)

Proof.

Consider two layers $U$ and $V$ whose alphabets are $[L]$ and $[R]$ and an edge constraint $e=(u,v)$ such that $u\in U$ and $v\in V$ . Let $\pi$ denote the projection constraint on $e$ . Let $f_{v}(\boldsymbol{x})=\chi_{\rho}(A_{v}(\boldsymbol{x}))$ , $g_{u}(\boldsymbol{x})=\chi_{\rho}(A_{u}(\boldsymbol{x}))$ and $h_{u}^{\boldsymbol{s}}(\boldsymbol{x})=\chi_{\rho}(A_{u}(\boldsymbol{x}\text{ % $\bullet$}\hskip 2.0pt\boldsymbol{s}))$ . With these notations, we have

\chi_{\rho}(A_{u}(\boldsymbol{y}))\cdot\chi_{\rho}(A_{u}(\boldsymbol{z}))=g_{u% }(\boldsymbol{y})\cdot h_{u}^{\boldsymbol{s}}(\boldsymbol{y}^{-1}\text{ $% \bullet$}\hskip 2.0pt(\boldsymbol{x}\circ\pi)^{-1})=(g_{u}*h_{u}^{\boldsymbol{% s}})((\boldsymbol{x}\circ\pi)^{-1}),

where $(\boldsymbol{x}\circ\pi)_{j}=x_{\pi(j)}$ . Thus, the inner expectation can be written as

	$\displaystyle\mathop{\mathbb{E}}_{\boldsymbol{x},\boldsymbol{s}}[f_{v}(% \boldsymbol{x})\cdot(g_{u}*h^{\boldsymbol{s}}_{u})((\boldsymbol{x}\circ\pi)^{-% 1})]$
	$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{x},\boldsymbol{s}}\left[\sum_{% \alpha\in\mathsf{Irrep}(G^{R})}\dim(\alpha)\mathsf{tr}(\hat{f_{v}}(\alpha)% \cdot\alpha(\boldsymbol{x}^{-1}))\sum_{\beta\in\mathsf{Irrep}(G^{L})}\dim(% \beta)\mathsf{tr}(\hat{g_{u}}(\beta)\hat{h_{u}^{\boldsymbol{s}}}(\beta)\cdot% \beta(\boldsymbol{x}\circ\pi))\right]$
	$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{x},\boldsymbol{s}}\left[\sum_{% \alpha,\beta}\dim(\alpha)\dim(\beta)\mathsf{tr}(\hat{f_{v}}(\alpha)\cdot\alpha% (\boldsymbol{x}^{-1}))\mathsf{tr}(\hat{g_{u}}(\beta)\hat{h_{u}^{\boldsymbol{s}% }}(\beta)\cdot\beta(\boldsymbol{x}\circ\pi))\right]$
	$\displaystyle=\sum_{\alpha,\beta}\dim(\alpha)\dim(\beta)\mathop{\mathbb{E}}_{% \boldsymbol{x},\boldsymbol{s}}\left[\mathsf{tr}(\hat{f_{v}}(\alpha)\cdot\alpha% (\boldsymbol{x}^{-1}))\mathsf{tr}(\hat{g_{u}}(\beta)\hat{h_{u}^{\boldsymbol{s}% }}(\beta)\cdot\beta(\boldsymbol{x}\circ\pi))\right].$

Denote

\mathbf{Term}^{e}(\alpha,\beta):=\dim(\alpha)\dim(\beta)\mathop{\mathbb{E}}_{% \boldsymbol{x},\boldsymbol{s}}[\mathsf{tr}(\hat{f_{v}}(\alpha)\cdot\alpha(% \boldsymbol{x}^{-1}))\mathsf{tr}(\hat{g_{u}}(\beta)\hat{h_{u}^{\boldsymbol{s}}% }(\beta)\cdot\beta(\boldsymbol{x}\circ\pi))],

we have

	$\displaystyle\mathbf{Term}^{e}(\alpha,\beta)$
	$\displaystyle=d_{\alpha}\dim(\beta)\mathop{\mathbb{E}}_{\boldsymbol{x},% \boldsymbol{s}}\left[\sum_{1\leqslant p,q\leqslant d_{\alpha}}\hat{f_{v}}(% \alpha)_{pq}\cdot\alpha(\boldsymbol{x}^{-1})_{qp}\sum_{1\leqslant i,k\leqslant% \dim(\beta)}\hat{g_{u}}(\beta)\hat{h_{u}^{\boldsymbol{s}}}(\beta)_{ik}\cdot% \beta(\boldsymbol{x}\circ\pi)_{ki}\right]$
	$\displaystyle=d_{\alpha}\dim(\beta)\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[% \sum_{p,q,i,k}\hat{f}_{v}(\alpha)_{pq}\cdot(\hat{g}_{u}(\beta)\hat{h^{% \boldsymbol{s}}_{u}}(\beta))_{ik}\cdot\mathop{\mathbb{E}}_{\boldsymbol{x}}% \left[\alpha(\boldsymbol{x}^{-1})_{qp}\cdot\beta(\boldsymbol{x}\circ\pi)_{ki}% \right]\right],$

where $(i,k)$ are the tuples $i=(i_{1},i_{2},\dots,i_{L})$ and $k=(k_{1},k_{2},\dots,k_{L})$ . Similarly, $(p,q)$ are tuples $p=(p_{1},p_{2},\dots,p_{R})$ and $q=(q_{1},q_{2},\dots,q_{R})$ . Then,

	$\displaystyle\mathop{\mathbb{E}}_{\boldsymbol{x}}\left[\alpha(\boldsymbol{x}^{% -1})_{qp}\cdot\beta(\boldsymbol{x}\circ\pi)_{ki}\right]$	$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{x}}\left[\prod_{l=1}^{R}\alpha_% {l}(x_{l}^{-1})_{q_{l}p_{l}}\prod_{l^{\prime}=1}^{L}\beta_{l^{\prime}}(x_{l^{% \prime}})_{k_{l^{\prime}}i_{l^{\prime}}}\right]$		(8)
		$\displaystyle=\prod_{l=1}^{R}\mathop{\mathbb{E}}_{\boldsymbol{x}}\left[\alpha_% {l}(x_{l}^{-1})_{q_{l}p_{l}}\prod_{l^{\prime}\in\pi^{-1}(l)}\beta_{l^{\prime}}% (x_{l^{\prime}})_{k_{l^{\prime}}i_{l^{\prime}}}\right].$		(9)

We argue that $s(\alpha)\subseteq\pi(s(\beta))$ to make this expression non-zero. Suppose that there exists a $\ell$ such that for all $\ell^{\prime}\in\pi^{-1}(\ell)$ , $\dim(\beta_{\ell^{\prime}})=1$ , then the product of all such $\beta_{\ell^{\prime}}$ must be 1 dimensional. According to Proposition 9, the expectation is $0$ unless $\alpha_{\ell}$ is also 1 dimensional and isomorphic to the product of $\beta_{\ell^{\prime}}$ . However, for an $\alpha_{l}\notin\widehat{G/H_{S}}$ , if $\beta_{\ell^{\prime}}\in\widehat{G/H_{S}}$ for all $\ell^{\prime}$ , then the product of $\beta_{\ell^{\prime}}$ belongs to $\widehat{G/H_{S}}$ and is not isomorphic to $\alpha_{\ell}$ . Therefore, for the expectation to be non-zero, there exists some $\ell^{\prime}$ such that $\beta_{\ell^{\prime}}\notin\widehat{G/H_{S}}$ , indicating $s(\alpha)\subseteq s(\beta)$ .

Define a function $F_{\beta}^{ki}(\boldsymbol{x}^{-1}):=\beta(\boldsymbol{x}\circ\pi)_{ki}$ , and note that

\sum_{i}\|F_{\beta}^{ki}\|_{2}^{2}=\sum_{i}\mathop{\mathbb{E}}_{\boldsymbol{x}% }[|{\beta}(\boldsymbol{x}^{-1}\circ\pi)_{ki}|^{2}]=\mathop{\mathbb{E}}_{% \boldsymbol{x}}\left[\sum_{i}|{\beta}(\boldsymbol{b}^{-1}\circ\pi)_{ki}|^{2}% \right]=1,

(10)

where the last equality follows from the fact that the sum expression is exactly the norm of the $k$ -th row of the representation $\beta$ . Since $\beta(.)$ is unitary, the norm of its row is always $1$ . Using the function $F_{\beta}^{ki}$ , we further simplify the expectation $\mathop{\mathbb{E}}_{\boldsymbol{x}}\left[\alpha(\boldsymbol{x}^{-1})_{qp}% \cdot\beta(\boldsymbol{x}\circ\pi)_{ki}\right]$ as follows.

	$\displaystyle\mathop{\mathbb{E}}_{\boldsymbol{x}}\left[\alpha(\boldsymbol{x}^{% -1})_{qp}\cdot\beta(\boldsymbol{x}\circ\pi)_{ki}\right]$	$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{x}}[\alpha(\boldsymbol{x}^{-1})% _{qp}F_{\beta}^{ki}(\boldsymbol{x}^{-1})]$
		$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{x}}\left[\alpha(\boldsymbol{x}^% {-1})_{qp}\sum_{\gamma}\dim(\gamma)\mathsf{tr}(\hat{F_{\beta}^{ki}}(\gamma)% \gamma(\boldsymbol{x}))\right]$
		$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{x}}\left[\sum_{\gamma}\dim(% \gamma)\sum_{p^{\prime},q^{\prime}}\hat{F_{\beta}^{ki}}(\gamma)_{p^{\prime}q^{% \prime}}\gamma(\boldsymbol{x})_{q^{\prime}p^{\prime}}\alpha(\boldsymbol{x}^{-1% })_{qp}\right]$
		$\displaystyle=\sum_{\gamma}\dim(\gamma)\sum_{p^{\prime},q^{\prime}}\hat{F_{% \beta}^{ki}}(\gamma)_{p^{\prime}q^{\prime}}\mathop{\mathbb{E}}_{\boldsymbol{x}% }\left[\gamma(\boldsymbol{x})_{q^{\prime}p^{\prime}}\alpha(\boldsymbol{x}^{-1}% )_{qp}\right].$

By Proposition 9, the expectation is $0$ unless $\alpha=\gamma$ , $p^{\prime}=q$ and $q^{\prime}=p$ . Hence, we have

\mathop{\mathbb{E}}_{\boldsymbol{x}}\left[\alpha(\boldsymbol{x}^{-1})_{qp}% \cdot\beta(\boldsymbol{x}\circ\pi)_{ki}\right]=\hat{F_{\beta}^{ki}}(\alpha)_{% pq}.

Thus, we can express $\mathbf{Term}^{e}(\alpha,\beta)$ as,

\mathbf{Term}^{e}(\alpha,\beta)=d_{\alpha}\dim(\beta)\sum_{p,q,i,k}\hat{f}_{v}% (\alpha)_{pq}\cdot\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[(\hat{g}_{u}(\beta% )\hat{h^{\boldsymbol{s}}_{u}}(\beta))_{ik}\right]\cdot\hat{F_{\beta}^{ki}}(% \alpha)_{pq}.

In addition, Lemma 15 indicates that $s(\alpha)$ and $s(\beta)$ are non-empty. Therefore,

\displaystyle\mathop{\mathbb{E}}_{\boldsymbol{x},\boldsymbol{s}}[f_{v}(% \boldsymbol{x})\cdot(g*h^{\boldsymbol{s}})((\boldsymbol{x}\circ\pi)^{-1})]

\displaystyle=\underbrace{\sum_{\begin{subarray}{c}\alpha,\beta\\ |s(\alpha)|,|s(\beta)|\neq 0\\ |s(\beta)|<C\\ s(\alpha)\subseteq\pi(s(\beta))\end{subarray}}\mathbf{Term}^{e}(\alpha,\beta)}% _{\Theta^{e(u,v)}_{\mathrm{Low}}}+\underbrace{\sum_{\begin{subarray}{c}\alpha,% \beta\\ |s(\alpha)|,|s(\beta)|\neq 0\\ |s(\beta)|\geqslant C\\ s(\alpha)\subseteq\pi(s(\beta))\end{subarray}}\mathbf{Term}^{e}(\alpha,\beta)}% _{\Theta^{e(u,v)}_{\mathrm{High}}},

where in the last expression we break the summation based on $|s(\beta)|$ .

If (7) is not true, then we have

\left|\mathop{\mathbb{E}}_{e(u,v)}\left[\Theta^{e(u,v)}_{\mathrm{Low}}+\Theta^% {e(u,v)}_{\mathrm{High}}\right]\right|\geqslant\delta^{\prime}.

where $\delta^{\prime}=\frac{\delta}{2|G|}$ . We will later show that that $\left|\mathop{\mathbb{E}}_{e(u,v)}\left[\Theta^{e(u,v)}_{\mathrm{High}}\right]% \right|\leqslant\delta^{\prime}/2$ . Assuming this, we have

\left|\mathop{\mathbb{E}}_{e(u,v)}\left[\Theta^{e(u,v)}_{\mathrm{Low}}\right]% \right|\geqslant\delta^{\prime}/2.

We now show how to come up with a decoding strategy based on the above lower bound.

Bounding the $\Theta^{e(u,v)}_{\mathrm{Low}}$ term.

Next, we argue that if $|\mathop{\mathbb{E}}_{e}[\Theta^{e(u,v)}_{\mathrm{Low}}]|$ is large, then we can decode an assignment to the Label Cover instance $\mathcal{H}$ . We first simplify the expression,

	$\displaystyle\|\Theta^{e(u,v)}_{\mathrm{Low}}\|^{2}$
	$\displaystyle=\left\|\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\sum_{\alpha,% \beta}\dim(\alpha)\dim(\beta)\sum_{p,q,i,k}\hat{f}_{v}(\alpha)_{pq}\cdot(\hat{% g}_{u}(\beta)\hat{h^{\boldsymbol{s}}_{u}}(\beta))_{ik}\cdot\hat{F_{\beta}^{ki}% }(\alpha)_{pq}\right]\right\|^{2}$
	$\displaystyle=\left\|\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\sum_{\alpha,% \beta}\dim(\alpha)\dim(\beta)\sum_{p,q,i,j,k}\hat{f}_{v}(\alpha)_{pq}\cdot\hat% {g}_{u}(\beta)_{ij}\cdot\hat{h^{\boldsymbol{s}}_{u}}(\beta)_{jk}\cdot\hat{F_{% \beta}^{ki}}(\alpha)_{pq}\right]\right\|^{2}$
	$\displaystyle\leqslant\left(\sum_{\alpha,\beta}d_{\alpha}d_{\beta}\sum_{\begin% {subarray}{c}p,q\\ i,j,k\end{subarray}}\|\hat{f}_{v}(\alpha)_{pq}\|^{2}\|\hat{g}_{u}(\beta)_{ij}\|^{2% }\right)\left(\sum_{\alpha,\beta}d_{\alpha}d_{\beta}\sum_{\begin{subarray}{c}p% ,q\\ i,j,k\end{subarray}}\|\hat{F}_{\beta}^{ki}(\alpha)_{pq}\|^{2}\mathop{\mathbb{E}}% _{\boldsymbol{s}}\left[\hat{h}_{u}^{\boldsymbol{s}}(\beta)_{jk}\right]^{2}\right)$

The second term is bounded by $1$ as

	$\displaystyle\sum_{\alpha,\beta}\dim(\alpha)\dim(\beta)\sum_{\begin{subarray}{% c}p,q\\ i,j,k\end{subarray}}\|\hat{F}_{\beta}^{ki}(\alpha)_{pq}\|^{2}\mathop{\mathbb{E}}% _{\boldsymbol{s}}\left[\hat{h}_{u}^{\boldsymbol{s}}(\beta)_{jk}\right]^{2}$
	$\displaystyle\leqslant\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\sum_{\beta}% \dim(\beta)\sum_{j,k}\|\hat{h}_{u}^{\boldsymbol{s}}(\beta)_{jk}\|^{2}\sum_{i}% \sum_{\alpha}\dim(\alpha)\sum_{p,q}\|\hat{F}_{\beta}^{ki}(\alpha)_{pq}\|^{2}\right]$
	$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\sum_{\beta}\dim(\beta% )\sum_{j,k}\|\hat{h}_{u}^{\boldsymbol{s}}(\beta)_{jk}\|^{2}\sum_{i}\\|F_{\beta}^{% ki}\\|^{2}\right]$
	$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\sum_{\beta}\dim(\beta% )\sum_{j,k}\|\hat{h}_{u}^{\boldsymbol{s}}(\beta)_{jk}\|^{2}\right]$		(Using Equation (10)
	$\displaystyle\leqslant\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\\|h_{u}^{% \boldsymbol{s}}\\|_{2}^{2}\right]=1,$

Based on the above bound, the term $|\Theta^{e(u,v)}_{\mathrm{Low}}|^{2}$ is upper bounded by

\displaystyle|\Theta^{e(u,v)}_{\mathrm{Low}}|^{2}

\displaystyle\leqslant\sum_{\begin{subarray}{c}\alpha,\beta\\ |s(\alpha)|,|s(\beta)|\neq 0\\ |s(\beta)|<C\\ s(\alpha)\subseteq\pi(s(\beta))\end{subarray}}\dim(\alpha)\dim(\beta)\sum_{% \begin{subarray}{c}p,q\\ i,j,k\end{subarray}}|\hat{f}_{v}(\alpha)_{pq}|^{2}|\hat{g}_{u}(\beta)_{ij}|^{2}

Since for $\beta$ such that $|s(\beta)|\leqslant C$ , $\dim(\beta)=\prod_{i=1}^{L}\dim(\beta_{i})=\prod_{i,\dim(\beta_{i})\geqslant 2% }\dim(\beta_{i})\leqslant(\sqrt{|G|})^{C}$ and the index $i$ varies over the dimension of $\beta$ ,

	$\displaystyle\|\Theta^{e(u,v)}_{\mathrm{Low}}\|^{2}$	$\displaystyle\leqslant\|G\|^{\frac{C}{2}}\sum_{\begin{subarray}{c}\alpha,\beta\\ \|s(\alpha)\|,\|s(\beta)\|\neq 0\\ \|s(\beta)\|<C\\ s(\alpha)\subseteq\pi(s(\beta))\end{subarray}}\dim(\alpha)\dim(\beta)\sum_{% \begin{subarray}{c}p,q\\ i,j\end{subarray}}\|\hat{f}_{v}(\alpha)_{pq}\|^{2}\|\hat{g}_{u}(\beta)_{ij}\|^{2}$
		$\displaystyle=\|G\|^{\frac{C}{2}}\sum_{\begin{subarray}{c}\alpha,\beta\\ \|s(\alpha)\|,\|s(\beta)\|\neq 0\\ \|s(\beta)\|<C\\ s(\alpha)\subseteq\pi(s(\beta))\end{subarray}}\dim(\alpha)\dim(\beta)\left\\|% \hat{f}_{v}(\alpha)\right\\|_{\mathsf{HS}}^{2}\left\\|\hat{g}_{u}(\beta)\right\\|% _{\mathsf{HS}}^{2}.$

Now, we can present the decoding strategy for a typical edge $e=(u,v)$ :

Decoding strategy.

1.

For each $u\in U$ , consider a function $g_{u}(\boldsymbol{x})=\chi_{\rho}(A_{u}(\boldsymbol{x}))$ , sample a $\beta$ with probability $\dim(\alpha)\left\|\hat{g}_{u}(\beta)\right\|_{\mathsf{HS}}^{2}$ and select a random coordinate $j$ s.t. $\chi_{\beta_{j}}\notin\widehat{G/H_{S}}$ . If there is no such $j$ , then return $\bot$ .
2.

For each $v\in V$ , consider a function $f_{v}(\boldsymbol{x})=\chi_{\rho}(A_{v}(\boldsymbol{x}))$ , sample an $\alpha$ with probability $\dim(\alpha)\left\|f_{v}(\alpha)\right\|_{\mathsf{HS}}^{2}$ and select a random coordinate $i$ s.t. $\chi_{\alpha_{i}}\notin\widehat{G/H_{S}}$ . If there is no such $i$ , then return $\bot$ .

For $\alpha,\beta$ such that $s(\alpha)$ , $s(\beta)$ are nonempty and $s(\alpha)\subseteq\pi(s(\beta))$ , the strategy will succeed with probability at least $1/|s(\beta)|$ . This is because for any label $\ell$ returned by player $v$ , the condition $s(\alpha)\subseteq\pi(s(\beta))$ guarantees that there exists a $\ell^{\prime}\in\pi^{-1}_{e}(\ell)$ such that $\beta_{\ell^{\prime}}\notin\widehat{G/H_{S}}$ , and the player $u$ returns this $\ell^{\prime}$ with probability $1/|s(\beta)|$ . Therefore, the expected value of the labeling returned by the strategy is given by

	$\displaystyle\mathop{\mathbb{E}}_{e(u,v)}\left[\sum_{\begin{subarray}{c}\alpha% ,\beta\\ \|s(\alpha)\|,\|s(\beta)\|\neq 0\\ \|s(\beta)\|<C\\ s(\alpha)\subseteq\pi(s(\beta))\end{subarray}}d_{\alpha}\dim(\beta)\left\\|\hat% {f}_{v}(\alpha)\right\\|_{\mathsf{HS}}^{2}\left\\|\hat{g}_{u}(\beta)\right\\|_{% \mathsf{HS}}^{2}\frac{1}{\|s(\beta)\|}\right]$
	$\displaystyle\geqslant\frac{1}{C}\mathop{\mathbb{E}}_{e(u,v)}\left[\sum_{% \begin{subarray}{c}\alpha,\beta\\ \|s(\alpha)\|,\|s(\beta)\|\neq 0\\ \|s(\beta)\|<C\\ s(\alpha)\subseteq\pi(s(\beta))\end{subarray}}\dim(\alpha)\dim(\beta)\left\\|% \hat{f}_{v}(\alpha)\right\\|_{\mathsf{HS}}^{2}\left\\|\hat{g}_{u}(\beta)\right\\|% _{\mathsf{HS}}^{2}\right]$
	$\displaystyle\geqslant\frac{1}{C\cdot\|G\|^{\frac{C}{2}}}\mathop{\mathbb{E}}_{e(% u,v)}\left[\|\Theta^{e(u,v)}_{\mathrm{Low}}\|^{2}\right]$
	$\displaystyle\geqslant\frac{1}{C\cdot\|G\|^{\frac{C}{2}}}\left\|\mathop{\mathbb{E% }}_{e(u,v)}\left[\Theta^{e(u,v)}_{\mathrm{Low}}\right]\right\|^{2}\geqslant% \frac{\delta^{\prime 2}}{4C\|G\|^{C/2}}.$		(Cauchy-Schwarz inequality)

We set $C=\Omega_{G}(r-2\log\delta^{\prime})$ so that $\frac{\delta^{\prime 2}}{4C|G|^{C/2}}>O(2^{-r})$ , which contradicts that hardness of Label Cover. Therefore, $|\mathop{\mathbb{E}}_{e(u,v)}[\Theta^{e(u,v)}_{\mathrm{Low}}]|\leqslant\delta^% {\prime}/4$ for any two layers in $\mathcal{H}$ , and hence

\left|\mathop{\mathbb{E}}_{1\leqslant t<t^{\prime}\leqslant T}\left[\mathop{% \mathbb{E}}_{\pi_{u,v}\in\Pi_{t,t^{\prime}}}\left[\Theta^{e(u,v)}_{\mathrm{Low% }}\right]\right]\right|\leqslant\frac{\delta^{\prime}}{4}.

Bounding the $\Theta^{e(u,v)}_{\mathrm{{High}}}$ term.

It remains to bound $|\mathop{\mathbb{E}}_{e}[\Theta^{e}_{\mathrm{{High}}}]|$ . We divide the term into two parts for $D$ such that $C\geqslant\Omega_{G}\left(\log{D}-\log{\delta^{\prime}}\right)$ .

\displaystyle\Theta^{e(u,v)}_{\mathrm{High}}

\displaystyle=\sum_{\begin{subarray}{c}\alpha,\beta\\ |s(\alpha)|,|s(\beta)|\neq 0\\ |s(\beta)|\geqslant C\\ s(\alpha)\subseteq\pi(s(\beta))\\ \dim(\beta)\leqslant D\end{subarray}}\mathbf{Term}^{e}(\alpha,\beta)+\sum_{% \begin{subarray}{c}\alpha,\beta\\ |s(\alpha)|,|s(\beta)|\neq 0\\ |s(\beta)|\geqslant C\\ s(\alpha)\subseteq\pi(s(\beta))\\ \dim(\beta)>D\end{subarray}}\mathbf{Term}^{e}(\alpha,\beta),

We denote the first term by $\Theta^{e(u,v)}_{\mathrm{High},\leqslant D}$ and the second term by $\Theta^{e(u,v)}_{\mathrm{High},>D}$ . We bound these terms separately.

Bounding $\Theta^{e(u,v)}_{\mathrm{High},\leqslant D}$ .

Starting with the simplified expression for $\mathbf{Term}^{e}(\alpha,\beta)$ , we have

\displaystyle\Theta^{e(u,v)}_{\mathrm{High},\leqslant D}=\sum_{\alpha,\beta}% \dim(\alpha)\dim(\beta)\sum_{p,q,i,k}\hat{f}_{v}(\alpha)_{pq}\cdot\mathop{% \mathbb{E}}_{\boldsymbol{s}}\left[(\hat{g}_{u}(\beta)\hat{h^{\boldsymbol{s}}_{% u}}(\beta))_{ik}\right]\cdot\hat{F_{\beta}^{ki}}(\alpha)_{pq}.

We now simplify the expectation over ${\boldsymbol{s}}$ . Recall that the function $h_{u}^{\boldsymbol{s}}(\boldsymbol{x}):=\chi_{\rho}(A_{u}(\boldsymbol{x}\text{% $\bullet$}\hskip 2.0pt\boldsymbol{s}))=g_{u}(\boldsymbol{x}\text{ $\bullet$}% \hskip 2.0pt\boldsymbol{s})$ . We now express the Fourier coefficient of $h_{u}^{\boldsymbol{s}}$ in terms of the Fourier coefficient of $g_{u}^{\boldsymbol{s}}$ . By the Fourier inversion formula,

$\displaystyle h_{u}^{\boldsymbol{s}}(\boldsymbol{x})=g_{u}(\boldsymbol{x}\text% { $\bullet$}\hskip 2.0pt\boldsymbol{s})$	$\displaystyle=\sum_{\beta}\dim(\beta)\mathsf{tr}(\hat{g}_{u}(\beta)\beta(% \boldsymbol{x}\text{ $\bullet$}\hskip 2.0pt\boldsymbol{s})^{\star})$
	$\displaystyle=\sum_{\beta}\dim(\beta)\mathsf{tr}(\hat{g}_{u}(\beta)(\beta(% \boldsymbol{x})\beta(\boldsymbol{s}))^{\star})$	(Using homomorphism of $\beta$ )
	$\displaystyle=\sum_{\beta}\dim(\beta)\mathsf{tr}(\hat{g}_{u}(\beta)\beta(% \boldsymbol{s})^{\star}\beta(\boldsymbol{x})^{\star})$

As the Fourier expansion is unique, we have $\hat{h}_{u}^{\boldsymbol{s}}(\beta)=\hat{g}_{u}(\beta)\beta(\boldsymbol{s})^{\star}$ . Using this, we have

	$\displaystyle\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[(\hat{g}_{u}(\beta)\hat% {h^{\boldsymbol{s}}_{u}}(\beta))_{ik}\right]$	$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[(\hat{g}_{u}(\beta)% \hat{g}_{u}(\beta)\beta(\boldsymbol{s}^{-1}))_{ik}\right]$
		$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\sum_{j,j^{\prime}}% \hat{g}_{u}(\beta)_{ij}\hat{g}_{u}(\beta)_{jj^{\prime}}\beta(\boldsymbol{s}^{-% 1})_{j^{\prime}k}\right]$
		$\displaystyle=\sum_{j,j^{\prime}}\hat{g}_{u}(\beta)_{ij}\hat{g}_{u}(\beta)_{jj% ^{\prime}}\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\beta(\boldsymbol{s}^{-1})% _{j^{\prime}k}\right]$
		$\displaystyle=\sum_{j,j^{\prime}}\hat{g}_{u}(\beta)_{ij}\hat{g}_{u}(\beta)_{jj% ^{\prime}}\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\prod_{\ell=1}^{L}\beta_{% \ell}(s_{\ell}^{-1})_{j^{\prime}_{\ell},k_{\ell}}\right]$
		$\displaystyle=\sum_{j,j^{\prime}}\hat{g}_{u}(\beta)_{ij}\hat{g}_{u}(\beta)_{jj% ^{\prime}}\prod_{\ell=1}^{L}\mathop{\mathbb{E}}_{\boldsymbol{s}_{\ell}}\left[% \beta_{\ell}(s_{\ell}^{-1})_{j^{\prime}_{\ell},k_{\ell}}\right]$

Now, we are in the setting when $\dim(\beta)\leqslant D$ but $s(\beta)\geqslant C$ . Hence, the number of dimension $\geqslant 2$ representations in $(\beta_{1},\beta_{2},\ldots,\beta_{L})$ is upper bounded by $\log_{2}D$ . Thus, there are at least $C-\log_{2}D$ coordinates $\ell\in[L]$ such that $\beta_{\ell}\notin\widehat{G/H_{S}}$ and $\dim(\beta_{\ell})=1$ . For each such $\beta_{\ell}$ we can apply the following claim.

Claim 17.

For $i$ such that $i\in s(\beta)$ , we have $\left\|\mathop{\mathbb{E}}_{s\sim S}[\beta_{i}(s)^{\star}]\right\|_{\mathsf{op% }}^{2}\leqslant 1-\delta_{G}$ for some $\delta_{G}>0$ .

Proof.

We refer the reader to the full version of the paper for the proof. $\hfill\vartriangleleft$

When $\dim(\beta_{\ell})=1$ and $\beta_{\ell}\notin\widehat{G/H_{S}}$ , the above claim gives

\exists\nobreak\ \varepsilon_{G}>0,\quad|\mathop{\mathbb{E}}_{s\in S}[\beta(s^% {-1})]|\leqslant 1-\varepsilon_{G}.

Correspondingly, we have

	$\displaystyle\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[(\hat{g}_{u}(\beta)\hat% {h^{\boldsymbol{s}}_{u}}(\beta))_{ik}\right]$	$\displaystyle=\sum_{j,j^{\prime}}\hat{g}_{u}(\beta)_{ij}\hat{g}_{u}(\beta)_{jj% ^{\prime}}\prod_{\ell=1}^{L}\mathop{\mathbb{E}}_{\boldsymbol{s}_{\ell}}\left[% \beta_{\ell}(s_{\ell}^{-1})_{j^{\prime}_{\ell},k_{\ell}}\right]$
		$\displaystyle\leqslant(1-\varepsilon_{G})^{(C-\log_{2}D)}\sum_{j,j^{\prime}}\|% \hat{g}_{u}(\beta)_{ij}\|\cdot\|\hat{g}_{u}(\beta)_{jj^{\prime}}\|.$

Plugging this upper bound, we get

	$\displaystyle\Theta^{e(u,v)}_{\mathrm{High},\leqslant D}$	$\displaystyle=\sum_{\alpha,\beta}\dim(\alpha)\dim(\beta)\sum_{p,q,i,k}\hat{f}_% {v}(\alpha)_{pq}\cdot\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[(\hat{g}_{u}(% \beta)\hat{h^{\boldsymbol{s}}_{u}}(\beta))_{ik}\right]\cdot\hat{F_{\beta}^{ki}% }(\alpha)_{pq}$
		$\displaystyle\leqslant(1-\varepsilon_{G})^{(C-\log_{2}D)}\sum_{\alpha,\beta}d_% {\alpha}d_{\beta}\sum_{\begin{subarray}{c}p,q,i,k\\ j,j^{\prime}\end{subarray}}\|\hat{f}_{v}(\alpha)_{pq}\|\cdot\|\hat{g}_{u}(\beta)_% {ij}\|\cdot\|\hat{g}_{u}(\beta)_{jj^{\prime}}\|\cdot\|\hat{F_{\beta}^{ki}}(\alpha)% _{pq}\|$

Applying the Cauchy-Schwarz inequality,

	$\displaystyle\|\Theta^{e(u,v)}_{\mathrm{High},\leqslant D}\|^{2}\leqslant(1-% \varepsilon_{G})^{2(C-\log_{2}D)}\left(\sum_{\alpha,\beta}\dim(\alpha)\dim(% \beta)\sum_{\begin{subarray}{c}p,q,i,k\\ j,j^{\prime}\end{subarray}}\|\hat{f}_{v}(\alpha)_{pq}\|^{2}\|\hat{g}_{u}(\beta)_{% ij}\|^{2}\right)$
	$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left(\sum_{% \alpha,\beta}\dim(\alpha)\dim(\beta)\sum_{\begin{subarray}{c}p,q,i,k\\ j,j^{\prime}\end{subarray}}\|\hat{F}_{\beta}^{ki}(\alpha)_{pq}\|^{2}\|\hat{g}_{u}% (\beta)_{jj^{\prime}}\|^{2}\right).$

Using the fact that $i,j,j^{\prime}$ and $k$ vary over the dimension of $\beta$ , which is at most $D$ , the first term is at most,

	$\displaystyle\left(\sum_{\alpha,\beta}\dim(\alpha)\dim(\beta)\sum_{\begin{% subarray}{c}p,q,i,k\\ j,j^{\prime}\end{subarray}}\|\hat{f}_{v}(\alpha)_{pq}\|^{2}\|\hat{g}_{u}(\beta)_{% ij}\|^{2}\right)$
	$\displaystyle\leqslant D^{2}\left(\sum_{\alpha}\dim(\alpha)\sum_{\begin{% subarray}{c}p,q\end{subarray}}\|\hat{f}_{v}(\alpha)_{pq}\|^{2}\right)\left(\sum_% {\beta}\dim(\beta)\sum_{\begin{subarray}{c}i,j\end{subarray}}\|\hat{g}_{u}(% \beta)_{ij}\|^{2}\right)\leqslant D^{2}\\|f_{v}\\|_{2}^{2}\\|g_{u}\\|_{2}^{2}% \leqslant D^{2}.$

Similarly, the second term is

	$\displaystyle\sum_{\alpha,\beta}\dim(\alpha)\dim(\beta)\sum_{\begin{subarray}{% c}p,q,i,k\\ j,j^{\prime}\end{subarray}}\|\hat{F}_{\beta}^{ki}(\alpha)_{pq}\|^{2}\|\hat{g}_{u}% (\beta)_{jj^{\prime}}\|^{2}$
	$\displaystyle\quad\quad\quad\leqslant D\sum_{\beta}\dim(\beta)\sum_{j,j^{% \prime}}\|\hat{h}_{u}^{\boldsymbol{s}}(\beta)_{jj^{\prime}}\|^{2}\sum_{i}\sum_{% \alpha}\dim(\alpha)\sum_{p,q}\|\hat{F}_{\beta}^{ki}(\alpha)_{pq}\|^{2}$
	$\displaystyle\quad\quad\quad=D\sum_{\beta}\dim(\beta)\sum_{jj^{\prime}}\|\hat{g% }_{u}(\beta)_{jj^{\prime}}\|^{2}\sum_{i}\\|F_{\beta}^{ki}\\|^{2}$
	$\displaystyle\quad\quad\quad=D\sum_{\beta}\dim(\beta)\sum_{j,j^{\prime}}\|\hat{% g}_{u}(\beta)_{jj^{\prime}}\|^{2}$		(Using Equation (10)
	$\displaystyle\quad\quad\quad\leqslant D\cdot\\|g_{u}\\|_{2}^{2}=D,$

Therefore, we have,

\left|\mathop{\mathbb{E}}_{e(u,v)}\left[\Theta^{e(u,v)}_{\mathrm{High},% \leqslant D}\right]\right|^{2}\leqslant\mathop{\mathbb{E}}_{e(u,v)}\left[|% \Theta^{e(u,v)}_{\mathrm{High},\leqslant D}|^{2}\right]\leqslant(1-\varepsilon% _{G})^{2(C-\log_{2}D)}D^{3}.

We verify that a setting of $D$ satisfies $(1-\varepsilon_{G})^{2(C-\log_{2}D)}D^{3}\leqslant\frac{\delta^{\prime 2}}{16}$ :

\displaystyle(1-\varepsilon_{G})^{2(C-\log_{2}D)}D^{3}\leqslant\frac{\delta^{% \prime 2}}{16}\implies C\geqslant\Omega_{G}\left(\log{D}-\log{\delta^{\prime}}% \right).

Bounding $\Theta^{e(u,v)}_{\mathrm{High},>D}$ .

We use the same high-degree argument as in the proof of the [4, Claim 4.5].

Claim 18.

For every edge $e=(u,v)$ , and $C=\Omega_{G}(\log(1/\delta^{\prime}))$ , we have $\left|\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\Theta^{e(u,v)}_{\mathrm{High}% ,>D}\right]\right|\leqslant\frac{\delta^{\prime}}{4}.$

Proof.

We refer the reader to the full version of the paper for the proof of this claim. $\hfill\vartriangleleft$

Finishing the proof.

Using these bounds, we have,

	$\displaystyle\left\|\mathop{\mathbb{E}}_{e(u,v)}\left[\Theta^{e(u,v)}_{\mathrm{% High}}\right]\right\|$	$\displaystyle=\left\|\mathop{\mathbb{E}}_{e(u,v)}\left[\Theta^{e(u,v)}_{\mathrm% {High},\leqslant D}+\Theta^{e(u,v)}_{\mathrm{High},>D}\right]\right\|$
		$\displaystyle\leqslant\left\|\mathop{\mathbb{E}}_{e(u,v)}\left[\Theta^{e(u,v)}_% {\mathrm{High},\leqslant D}\right]\right\|+\left\|\mathop{\mathbb{E}}_{e(u,v)}% \left[\Theta^{e(u,v)}_{\mathrm{High},>D}\right]\right\|\leqslant\frac{\delta^{% \prime}}{4}+\frac{\delta^{\prime}}{4}=\frac{\delta^{\prime}}{2}\leqslant\frac{% \delta}{4\|G\|},$

as required. $\hfill\blacktriangleleft$ Therefore, the term (5) collectively can be upper bounded by $\frac{\delta}{2}$ .

4.2.2 Bounding expressions in (6)

The analysis for representations with $\dim(\rho)\geqslant 2$ shares structural similarities with the proof of Max-3LIN over non-abelian groups in [4]. However, our setting introduces additional noise terms $\boldsymbol{s}\in S^{R_{t}}$ and $s\in S$ that must be carefully handled. We provide a high-level proof outline here and defer the exhaustive algebraic expansion to the full version of the paper. The core of the bound relies on the following lemma:

Lemma 19.

Let $K:=\frac{8|G|^{10}}{\delta^{2}}$ . If the Layered Label Cover instance $\mathcal{H}$ is at most $\min\left(\frac{\delta^{2}}{10|G|^{10K}},\frac{\delta^{2}}{2|G|^{20}}\right)$ -satisfiable, then

\left|\mathop{\mathbb{E}}_{1\leqslant t<t^{\prime}\leqslant T}\left[\mathop{% \mathbb{E}}_{\pi_{uv}\in\Pi_{t,t^{\prime}}}\left[\mathop{\mathbb{E}}_{% \boldsymbol{x},\boldsymbol{y},\boldsymbol{z}}[\chi_{\rho}(A_{v}(\boldsymbol{x}% )\text{ $\bullet$}\hskip 2.0ptA_{u}(\boldsymbol{y})\text{ $\bullet$}\hskip 2.0% ptA_{u}(\boldsymbol{z})\text{ $\bullet$}\hskip 2.0pts^{-1})]\right]\right]% \right|\leqslant\frac{\delta}{|G|^{3}}.

Proof Sketch.

The analysis for representations with $\dim(\rho)\geqslant 2$ is structurally similar to the analysis in [5]. By fixing a noise vector $\boldsymbol{s}$ , we can follow the approach in [5]. we introduce a threshold parameter $K:=\frac{8|G|^{10}}{\delta^{2}}$ to divide the remaining summation into a low-degree component ( $\Gamma_{\mathrm{low}}$ ) and a high-degree component ( $\Gamma_{\mathrm{high}}$ ), based on whether the number of dimensions $\geqslant 2$ in the representation $\beta$ is strictly less than $K$ or at least $K$ . See the full version of the paper for the actual proof. $\hfill\blacktriangleleft$

By summing the result of Lemma 19 over all representations $\rho$ with $\dim(\rho)\geqslant 2$ and all $s\in S$ , the total contribution to the expectation is at most $\frac{\delta}{2}$ .

Combining this with the bound of $\frac{\delta}{2}$ on the terms for $1$ -dimensional representations (Equation 5), we conclude that if the Layered Label Cover instance is at most $2^{-r}$ -satisfiable, then $\text{value}(A)\leqslant\frac{|S|}{|H_{S}|}+\delta$ . This completes the proof of Lemma 14. $\hfill\blacktriangleleft$

References

[1] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM), 45(3):501–555, 1998. doi:10.1145/278298.278306.
[2] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM (JACM), 45(1):70–122, 1998. doi:10.1145/273865.273901.
[3] 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.
[4] Amey Bhangale and Subhash Khot. Optimal inapproximability of satisfiable k-lin over non-abelian groups. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1615–1628. ACM, 2021. doi:10.1145/3406325.3451003.
[5] Amey Bhangale and Subhash Khot. Optimal inapproximability of satisfiable k-LIN over non-abelian groups. (updated paper), 2026.
[6] Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable k-CSPs: I. In 54th Annual Symposium on Theory of Computing (STOC’22), pages 976–988, New York, NY, USA, 2022. ACM. doi:10.1145/3519935.3520028.
[7] Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable K-CSPs: II. In 55th Annual Symposium on Theory of Computing (STOC’23), pages 632–642, New York, NY, USA, 2023. ACM. doi:10.1145/3564246.3585120.
[8] Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k-csps: Iv. In 56th Annual Symposium on Theory of Computing (STOC’24), pages 1423–1434, New York, NY, USA, 2024. ACM. doi:10.1145/3618260.3649610.
[9] Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k-csps: V, 2025. doi:10.1145/3717823.3718127.
[10] Mark Braverman, Subhash Khot, and Dor Minzer. On rich 2-to-1 games. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, Virtual Conference, January 6-8, 2021, LIPIcs, pages 27:1–27:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ITCS.2021.27.
[11] Andrei A. Bulatov. A dichotomy theorem for nonuniform csps. In 58th Annual Symposium on Foundations of Computer Science (FOCS’17), pages 319–330, Piscataway, NJ, USA, 2017. IEEE. doi:10.1109/FOCS.2017.37.
[12] Siu On Chan. Approximation resistance from pairwise-independent subgroups. Journal of the ACM (JACM), 63(3):1–32, 2016. doi:10.1145/2873054.
[13] Arkadev Chattopadhyay and Avi Wigderson. Linear Systems over Composite Moduli . In 50th Annual Symposium on Foundations of Computer Science (FOCS’09), Los Alamitos, CA, USA, October 2009. IEEE. doi:10.1109/FOCS.2009.17.
[14] Irit Dinur and Venkatesan Guruswami. PCPs via low-degree long code and hardness for constrained hypergraph coloring. In 54th Annual Symposium on Foundations of Computer Science (FOCS’13), pages 340–349, Piscataway, NJ, USA, 2013. IEEE. doi:10.1109/FOCS.2013.44.
[15] Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev. A new multilayered pcp and the hardness of hypergraph vertex cover. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’03, pages 595–601, New York, NY, USA, 2003. Association for Computing Machinery. doi:10.1145/780542.780629.
[16] Lars Engebretsen, Jonas Holmerin, and Alexander Russell. Inapproximability results for equations over finite groups. Theoretical Computer Science, 312(1):17–45, 2004. doi:10.1016/S0304-3975(03)00401-8.
[17] Tomás Feder and Moshe Y. Vardi. Monotone monadic SNP and constraint satisfaction. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 612–622. ACM, 1993. doi:10.1145/167088.167245.
[18] Tomás Feder and Moshe Y Vardi. The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing, 28(1):57–104, 1998. doi:10.1137/S0097539794266766.
[19] Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM (JACM), 43(2):268–292, 1996. doi:10.1145/226643.226652.
[20] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1115–1145, 1995. doi:10.1145/227683.227684.
[21] Mikael Goldmann and Alexander Russell. The complexity of solving equations over finite groups. Information and Computation, 178(1):253–262, 2002. doi:10.1006/inco.2002.3173.
[22] Venkatesan Guruswami, Johan Hastad, and Madhu Sudan. Hardness of approximate hypergraph coloring. SIAM Journal on Computing, 31(6):1663–1686, 2002. doi:10.1137/S0097539700377165.
[23] Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar. Beating the random ordering is hard: Every ordering csp is approximation resistant. SIAM Journal on Computing, 40(3):878–914, 2011. doi:10.1137/090756144.
[24] Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798–859, 2001. doi:10.1145/502090.502098.
[25] Johan Håstad. Satisfying degree- $d$ equations over $gf[2]^{n}$ . Theory of Computing, 9(27):845–862, 2013. doi:10.4086/toc.2013.v009a027.
[26] Johan Håstad. On the np-hardness of max-not-2. SIAM Journal on Computing, 43(1):179–193, 2014. doi:10.1137/120882718.
[27] Subhash Khot. Hardness results for approximate hypergraph coloring. In 34th Annual Symposium on Theory of Computing (STOC’02), pages 351–359, New York, NY, USA, 2002. ACM. doi:10.1145/509907.509962.
[28] Subhash Khot. Hardness results for coloring 3 -colorable 3 -uniform hypergraphs. In 43rd Annual Symposium on Foundations of Computer Science (FOCS’02), pages 23–32, Piscataway, NJ, USA, 2002. IEEE. doi:10.1109/SFCS.2002.1181879.
[29] Subhash Khot. On the power of unique 2-prover 1-round games. In 34th Annual Symposium on Theory of Computing (STOC’02), pages 767–775, New York, NY, USA, 2002. ACM, ACM. doi:10.1145/509907.510017.
[30] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? SIAM Journal on Computing, 37(1):319–357, 2007. doi:10.1137/S0097539705447372.
[31] Subhash Khot and Muli Safra. A two-prover one-round game with strong soundness. Theory of Computing, 9:863–887, 2013. doi:10.4086/toc.2013.v009a028.
[32] Ryan O’Donnell. Analysis of boolean functions. Cambridge University Press, USA, 2014. doi:10.1017/CBO9781139814782.
[33] Prasad Raghavendra. Approximating np-hard problems efficient algorithms and their limits. PhD thesis, University of Washington, Seattle, WA, USA, 2009. AAI3377316. doi:10.5555/1751149.
[34] Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763–803, 1998. doi:10.1137/S0097539795280895.
[35] Alex Samorodnitsky and Luca Trevisan. A pcp characterization of np with optimal amortized query complexity. In 32nd Annual Symposium on Theory of Computing (STOC’00), pages 191–199, New York, NY, USA, 2000. ACM. doi:10.1145/335305.335329.
[36] Thomas J. Schaefer. The complexity of satisfiability problems. In 10th Annual Symposium on Theory of Computing (STOC’78), pages 216–226, New York, NY, USA, 1978. ACM. doi:10.1145/800133.804350.
[37] Audrey Terras. Fourier analysis on finite groups and applications. Cambridge University Press, USA, 1999. doi:10.1017/CBO9780511626265.
[38] Dmitriy Zhuk. A proof of the csp dichotomy conjecture. Journal of the ACM (JACM), 67(5), August 2020. doi:10.1145/3402029.

[bib.bib1] [1] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM), 45(3):501–555, 1998. doi:10.1145/278298.278306.

[bib.bib2] [2] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM (JACM), 45(1):70–122, 1998. doi:10.1145/273865.273901.

[bib.bib3] [3] 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.

[bib.bib4] [4] Amey Bhangale and Subhash Khot. Optimal inapproximability of satisfiable k-lin over non-abelian groups. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1615–1628. ACM, 2021. doi:10.1145/3406325.3451003.

[bib.bib5] [5] Amey Bhangale and Subhash Khot. Optimal inapproximability of satisfiable k-LIN over non-abelian groups. (updated paper), 2026.

[bib.bib6] [6] Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable k-CSPs: I. In 54th Annual Symposium on Theory of Computing (STOC’22), pages 976–988, New York, NY, USA, 2022. ACM. doi:10.1145/3519935.3520028.

[bib.bib7] [7] Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable K-CSPs: II. In 55th Annual Symposium on Theory of Computing (STOC’23), pages 632–642, New York, NY, USA, 2023. ACM. doi:10.1145/3564246.3585120.

[bib.bib8] [8] Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k-csps: Iv. In 56th Annual Symposium on Theory of Computing (STOC’24), pages 1423–1434, New York, NY, USA, 2024. ACM. doi:10.1145/3618260.3649610.

[bib.bib9] [9] Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k-csps: V, 2025. doi:10.1145/3717823.3718127.

[bib.bib10] [10] Mark Braverman, Subhash Khot, and Dor Minzer. On rich 2-to-1 games. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, Virtual Conference, January 6-8, 2021, LIPIcs, pages 27:1–27:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ITCS.2021.27.

[bib.bib11] [11] Andrei A. Bulatov. A dichotomy theorem for nonuniform csps. In 58th Annual Symposium on Foundations of Computer Science (FOCS’17), pages 319–330, Piscataway, NJ, USA, 2017. IEEE. doi:10.1109/FOCS.2017.37.

[bib.bib12] [12] Siu On Chan. Approximation resistance from pairwise-independent subgroups. Journal of the ACM (JACM), 63(3):1–32, 2016. doi:10.1145/2873054.

[bib.bib13] [13] Arkadev Chattopadhyay and Avi Wigderson. Linear Systems over Composite Moduli . In 50th Annual Symposium on Foundations of Computer Science (FOCS’09), Los Alamitos, CA, USA, October 2009. IEEE. doi:10.1109/FOCS.2009.17.

[bib.bib14] [14] Irit Dinur and Venkatesan Guruswami. PCPs via low-degree long code and hardness for constrained hypergraph coloring. In 54th Annual Symposium on Foundations of Computer Science (FOCS’13), pages 340–349, Piscataway, NJ, USA, 2013. IEEE. doi:10.1109/FOCS.2013.44.

[bib.bib15] [15] Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev. A new multilayered pcp and the hardness of hypergraph vertex cover. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’03, pages 595–601, New York, NY, USA, 2003. Association for Computing Machinery. doi:10.1145/780542.780629.

[bib.bib16] [16] Lars Engebretsen, Jonas Holmerin, and Alexander Russell. Inapproximability results for equations over finite groups. Theoretical Computer Science, 312(1):17–45, 2004. doi:10.1016/S0304-3975(03)00401-8.

[bib.bib17] [17] Tomás Feder and Moshe Y. Vardi. Monotone monadic SNP and constraint satisfaction. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 612–622. ACM, 1993. doi:10.1145/167088.167245.

[bib.bib18] [18] Tomás Feder and Moshe Y Vardi. The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing, 28(1):57–104, 1998. doi:10.1137/S0097539794266766.

[bib.bib19] [19] Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM (JACM), 43(2):268–292, 1996. doi:10.1145/226643.226652.

[bib.bib20] [20] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1115–1145, 1995. doi:10.1145/227683.227684.

[bib.bib21] [21] Mikael Goldmann and Alexander Russell. The complexity of solving equations over finite groups. Information and Computation, 178(1):253–262, 2002. doi:10.1006/inco.2002.3173.

[bib.bib22] [22] Venkatesan Guruswami, Johan Hastad, and Madhu Sudan. Hardness of approximate hypergraph coloring. SIAM Journal on Computing, 31(6):1663–1686, 2002. doi:10.1137/S0097539700377165.

[bib.bib23] [23] Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar. Beating the random ordering is hard: Every ordering csp is approximation resistant. SIAM Journal on Computing, 40(3):878–914, 2011. doi:10.1137/090756144.

[bib.bib24] [24] Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798–859, 2001. doi:10.1145/502090.502098.

[bib.bib25] [25] Johan Håstad. Satisfying degree- $d$ equations over $gf[2]^{n}$ . Theory of Computing, 9(27):845–862, 2013. doi:10.4086/toc.2013.v009a027.

[bib.bib26] [26] Johan Håstad. On the np-hardness of max-not-2. SIAM Journal on Computing, 43(1):179–193, 2014. doi:10.1137/120882718.

[bib.bib27] [27] Subhash Khot. Hardness results for approximate hypergraph coloring. In 34th Annual Symposium on Theory of Computing (STOC’02), pages 351–359, New York, NY, USA, 2002. ACM. doi:10.1145/509907.509962.

[bib.bib28] [28] Subhash Khot. Hardness results for coloring 3 -colorable 3 -uniform hypergraphs. In 43rd Annual Symposium on Foundations of Computer Science (FOCS’02), pages 23–32, Piscataway, NJ, USA, 2002. IEEE. doi:10.1109/SFCS.2002.1181879.

[bib.bib29] [29] Subhash Khot. On the power of unique 2-prover 1-round games. In 34th Annual Symposium on Theory of Computing (STOC’02), pages 767–775, New York, NY, USA, 2002. ACM, ACM. doi:10.1145/509907.510017.

[bib.bib30] [30] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? SIAM Journal on Computing, 37(1):319–357, 2007. doi:10.1137/S0097539705447372.

[bib.bib31] [31] Subhash Khot and Muli Safra. A two-prover one-round game with strong soundness. Theory of Computing, 9:863–887, 2013. doi:10.4086/toc.2013.v009a028.

[bib.bib32] [32] Ryan O’Donnell. Analysis of boolean functions. Cambridge University Press, USA, 2014. doi:10.1017/CBO9781139814782.

[bib.bib33] [33] Prasad Raghavendra. Approximating np-hard problems efficient algorithms and their limits. PhD thesis, University of Washington, Seattle, WA, USA, 2009. AAI3377316. doi:10.5555/1751149.

[bib.bib34] [34] Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763–803, 1998. doi:10.1137/S0097539795280895.

[bib.bib35] [35] Alex Samorodnitsky and Luca Trevisan. A pcp characterization of np with optimal amortized query complexity. In 32nd Annual Symposium on Theory of Computing (STOC’00), pages 191–199, New York, NY, USA, 2000. ACM. doi:10.1145/335305.335329.

[bib.bib36] [36] Thomas J. Schaefer. The complexity of satisfiability problems. In 10th Annual Symposium on Theory of Computing (STOC’78), pages 216–226, New York, NY, USA, 1978. ACM. doi:10.1145/800133.804350.

[bib.bib37] [37] Audrey Terras. Fourier analysis on finite groups and applications. Cambridge University Press, USA, 1999. doi:10.1017/CBO9780511626265.

[bib.bib38] [38] Dmitriy Zhuk. A proof of the csp dichotomy conjecture. Journal of the ACM (JACM), 67(5), August 2020. doi:10.1145/3402029.

	$\displaystyle\|\Theta^{e(u,v)}_{\mathrm{Low}}\|^{2}$
	$\displaystyle=\left\|\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\sum_{\alpha,% \beta}\dim(\alpha)\dim(\beta)\sum_{p,q,i,k}\hat{f}_{v}(\alpha)_{pq}\cdot(\hat{% g}_{u}(\beta)\hat{h^{\boldsymbol{s}}_{u}}(\beta))_{ik}\cdot\hat{F_{\beta}^{ki}% }(\alpha)_{pq}\right]\right\|^{2}$
	$\displaystyle=\left\|\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\sum_{\alpha,% \beta}\dim(\alpha)\dim(\beta)\sum_{p,q,i,j,k}\hat{f}_{v}(\alpha)_{pq}\cdot\hat% {g}_{u}(\beta)_{ij}\cdot\hat{h^{\boldsymbol{s}}_{u}}(\beta)_{jk}\cdot\hat{F_{% \beta}^{ki}}(\alpha)_{pq}\right]\right\|^{2}$
	$\displaystyle\leqslant\left(\sum_{\alpha,\beta}d_{\alpha}d_{\beta}\sum_{\begin% {subarray}{c}p,q\\ i,j,k\end{subarray}}\|\hat{f}_{v}(\alpha)_{pq}\|^{2}\|\hat{g}_{u}(\beta)_{ij}\|^{2% }\right)\left(\sum_{\alpha,\beta}d_{\alpha}d_{\beta}\sum_{\begin{subarray}{c}p% ,q\\ i,j,k\end{subarray}}\|\hat{F}_{\beta}^{ki}(\alpha)_{pq}\|^{2}\mathop{\mathbb{E}}% _{\boldsymbol{s}}\left[\hat{h}_{u}^{\boldsymbol{s}}(\beta)_{jk}\right]^{2}\right)$

	$\displaystyle\sum_{\alpha,\beta}\dim(\alpha)\dim(\beta)\sum_{\begin{subarray}{% c}p,q\\ i,j,k\end{subarray}}\|\hat{F}_{\beta}^{ki}(\alpha)_{pq}\|^{2}\mathop{\mathbb{E}}% _{\boldsymbol{s}}\left[\hat{h}_{u}^{\boldsymbol{s}}(\beta)_{jk}\right]^{2}$
	$\displaystyle\leqslant\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\sum_{\beta}% \dim(\beta)\sum_{j,k}\|\hat{h}_{u}^{\boldsymbol{s}}(\beta)_{jk}\|^{2}\sum_{i}% \sum_{\alpha}\dim(\alpha)\sum_{p,q}\|\hat{F}_{\beta}^{ki}(\alpha)_{pq}\|^{2}\right]$
	$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\sum_{\beta}\dim(\beta% )\sum_{j,k}\|\hat{h}_{u}^{\boldsymbol{s}}(\beta)_{jk}\|^{2}\sum_{i}\\|F_{\beta}^{% ki}\\|^{2}\right]$
	$\displaystyle=\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\sum_{\beta}\dim(\beta% )\sum_{j,k}\|\hat{h}_{u}^{\boldsymbol{s}}(\beta)_{jk}\|^{2}\right]$		(Using Equation (10)
	$\displaystyle\leqslant\mathop{\mathbb{E}}_{\boldsymbol{s}}\left[\\|h_{u}^{% \boldsymbol{s}}\\|_{2}^{2}\right]=1,$

	$\displaystyle\mathop{\mathbb{E}}_{e(u,v)}\left[\sum_{\begin{subarray}{c}\alpha% ,\beta\\ \|s(\alpha)\|,\|s(\beta)\|\neq 0\\ \|s(\beta)\|<C\\ s(\alpha)\subseteq\pi(s(\beta))\end{subarray}}d_{\alpha}\dim(\beta)\left\\|\hat% {f}_{v}(\alpha)\right\\|_{\mathsf{HS}}^{2}\left\\|\hat{g}_{u}(\beta)\right\\|_{% \mathsf{HS}}^{2}\frac{1}{\|s(\beta)\|}\right]$
	$\displaystyle\geqslant\frac{1}{C}\mathop{\mathbb{E}}_{e(u,v)}\left[\sum_{% \begin{subarray}{c}\alpha,\beta\\ \|s(\alpha)\|,\|s(\beta)\|\neq 0\\ \|s(\beta)\|<C\\ s(\alpha)\subseteq\pi(s(\beta))\end{subarray}}\dim(\alpha)\dim(\beta)\left\\|% \hat{f}_{v}(\alpha)\right\\|_{\mathsf{HS}}^{2}\left\\|\hat{g}_{u}(\beta)\right\\|% _{\mathsf{HS}}^{2}\right]$
	$\displaystyle\geqslant\frac{1}{C\cdot\|G\|^{\frac{C}{2}}}\mathop{\mathbb{E}}_{e(% u,v)}\left[\|\Theta^{e(u,v)}_{\mathrm{Low}}\|^{2}\right]$
	$\displaystyle\geqslant\frac{1}{C\cdot\|G\|^{\frac{C}{2}}}\left\|\mathop{\mathbb{E% }}_{e(u,v)}\left[\Theta^{e(u,v)}_{\mathrm{Low}}\right]\right\|^{2}\geqslant% \frac{\delta^{\prime 2}}{4C\|G\|^{C/2}}.$		(Cauchy-Schwarz inequality)

	$\displaystyle\sum_{\alpha,\beta}\dim(\alpha)\dim(\beta)\sum_{\begin{subarray}{% c}p,q,i,k\\ j,j^{\prime}\end{subarray}}\|\hat{F}_{\beta}^{ki}(\alpha)_{pq}\|^{2}\|\hat{g}_{u}% (\beta)_{jj^{\prime}}\|^{2}$
	$\displaystyle\quad\quad\quad\leqslant D\sum_{\beta}\dim(\beta)\sum_{j,j^{% \prime}}\|\hat{h}_{u}^{\boldsymbol{s}}(\beta)_{jj^{\prime}}\|^{2}\sum_{i}\sum_{% \alpha}\dim(\alpha)\sum_{p,q}\|\hat{F}_{\beta}^{ki}(\alpha)_{pq}\|^{2}$
	$\displaystyle\quad\quad\quad=D\sum_{\beta}\dim(\beta)\sum_{jj^{\prime}}\|\hat{g% }_{u}(\beta)_{jj^{\prime}}\|^{2}\sum_{i}\\|F_{\beta}^{ki}\\|^{2}$
	$\displaystyle\quad\quad\quad=D\sum_{\beta}\dim(\beta)\sum_{j,j^{\prime}}\|\hat{% g}_{u}(\beta)_{jj^{\prime}}\|^{2}$		(Using Equation (10)
	$\displaystyle\quad\quad\quad\leqslant D\cdot\\|g_{u}\\|_{2}^{2}=D,$

Optimal Inapproximability of Generalized Linear Equations over a Finite Group

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Definition 1 (Max-Ek-LINS⁢(G)).

Approximation Algorithm for Max-E𝟑-LIN𝑺⁢(𝑮)

Theorem 2.

1.1 Related Work

1.2 Techniques

1.2.1 Abelian Groups

Decoding Strategy

Modified low-degree influences

Modified Decoding Strategy

1.2.2 Non-abelian Groups

▶ Remark 3.

1.3 Organization

2 Preliminaries

2.1 Label Cover

Definition 4 (Label Cover).

Theorem 5 (Hardness of Label Cover).

Definition 6 (Layered Label Cover).

Theorem 7 ([15], Hardness of Layered Label Cover).

2.2 Fourier analysis over non-abelian group

Fact 8.

Proposition 9.

Proposition 10.

Proposition 11 (Orthogonality of characters).

Proposition 12.

3 An Approximation Algorithm

Theorem 13.

Proof.

4 Hardness of Max-E𝟑-LIN𝑺⁢(𝑮)

Main Reduction

4.1 Completeness

4.2 Soundness

Lemma 14.

Proof.

4.2.1 Bounding expressions in (5)

Lemma 15.

Proof.

Lemma 16.

Proof.

Bounding the 𝚯𝐋𝐨𝐰𝒆⁢(𝒖,𝒗) term.

Decoding strategy.

Bounding the 𝚯𝐇𝐢𝐠𝐡𝒆⁢(𝒖,𝒗) term.

Bounding 𝚯𝐇𝐢𝐠𝐡,⩽𝑫𝒆⁢(𝒖,𝒗).

Claim 17.

Proof.

Bounding 𝚯𝐇𝐢𝐠𝐡,>𝑫𝒆⁢(𝒖,𝒗).

Claim 18.

Proof.

Finishing the proof.

4.2.2 Bounding expressions in (6)

Lemma 19.

Proof Sketch.

References

Definition 1 ( $\text{Max-E$k$-LIN}_{S}(G)$ ).

Approximation Algorithm for $\text{Max-E$3$-LIN}_{S}(G)$

$\blacktriangleright$ Remark 3.

4 Hardness of $\text{Max-E$3$-LIN}_{S}(G)$

Bounding the $\Theta^{e(u,v)}_{\mathrm{Low}}$ term.

Bounding the $\Theta^{e(u,v)}_{\mathrm{{High}}}$ term.

Bounding $\Theta^{e(u,v)}_{\mathrm{High},\leqslant D}$ .

Bounding $\Theta^{e(u,v)}_{\mathrm{High},>D}$ .