Hardness of the Binary Covering Radius Problem in Large ℓ p \ell_{p} Norms Huck Bennett, Peter Ly Abstract We study the hardness of the γ \gamma -approximate decisional Covering Radius Problem on lattices in the ℓ p \ell_{p} norm ( γ \gamma - GapCRP p \mathrm{GapCRP}_{p} ). Specifically, we prove that there is an explicit function γ ⁡ ( p ) \gamma(p) , with γ ⁡ ( p ) > 1 \gamma(p)>1 for p > p 0 ≈ 35.31 p>p_{0}\approx 35.31 and lim p → ∞ γ ⁡ ( p ) = 9 / 8 \lim_{p\to\infty}\gamma(p)=9/8 , such that for any constant ε > 0 \varepsilon>0 , ( γ ⁡ ( p ) − ε ) (\gamma(p)-\varepsilon) - GapCRP p \mathrm{GapCRP}_{p} is 𝖭𝖯 \mathsf{NP} -hard. This shows the first hardness of GapCRP p \mathrm{GapCRP}_{p} for explicit p < ∞ p<\infty . Work of Haviv and Regev (CCC, 2006 and CJTCS, 2012) previously showed Π 2 \Pi_{2} -hardness of approximation for GapCRP p \mathrm{GapCRP}_{p} for all sufficiently large (but non-explicit) finite p p and for p = ∞ p=\infty . In fact, our hardness results hold for a variant of GapCRP \mathrm{GapCRP} called the Binary Covering Radius Problem ( BinGapCRP \mathrm{BinGapCRP} ), which trivially reduces to both GapCRP \mathrm{GapCRP} and the decisional Linear Discrepancy Problem ( LinDisc \mathrm{LinDisc} ) in any norm in an approximation-preserving way. We also show Π 2 \Pi_{2} -hardness of ( 9 / 8 − ε ) (9/8-\varepsilon) - BinGapCRP \mathrm{BinGapCRP} in the ℓ ∞ \ell_{\infty} norm for any constant ε > 0 \varepsilon>0 . Our work extends and heavily uses the work of Manurangsi (IPL, 2021), which showed Π 2 \Pi_{2} -hardness of ( 9 / 8 − ε ) (9/8-\varepsilon) - LinDisc \mathrm{LinDisc} in the ℓ ∞ \ell_{\infty} norm. 1 Introduction 10^{1} 10^{2} 10^{3} 10^{4} 1 1.1 p \gamma \gamma(p) 9/8 Figure 1: A linear-log plot of the approximation factor \gamma=\gamma(p) for which we show \mathsf{NP} -hardness of (\gamma-\varepsilon) - \mathrm{BinGapCRP} in the \ell_{p} norm (in blue ; see Theorem 1.1 ). The function \gamma(p) , specified in Equation 1 , is greater than 1 for all p>p_{0}=35.310188... and satisfies \lim_{p\to\infty}\gamma(p)=9/8 . (The blue dot is at the point (p,\gamma)=(p_{0},1) , where p_{0} is the unique value of p such that \gamma(p)=1 . The horizontal asymptote of 9/8 is shown in red .) This factor of 9/8 also appears in our \Pi_{2} -hardness result for \mathrm{BinGapCRP}_{\infty} ( Theorem 1.2 ) and in the work of Manurangsi [ Man21 ] on \mathrm{LinDisc} , which is the foundation of our work. The covering radius \mu(\mathcal{L}) of a lattice \mathcal{L} is the maximum distance of a point in the span of \mathcal{L} to a vector in \mathcal{L} . It is one of the most fundamental lattice quantities. Accordingly, the (decisional) Covering Radius Problem ((Gap) \mathrm{CRP} ) is among the most fundamental lattice problems. Indeed, it is connected to the main applications of lattices in computer science. Approximate \mathrm{GapCRP} is one of the worst-case problems from which there is a reduction to the average-case problems used in lattice-based cryptography [ Mic02 ] , and it is related to fast algorithms for integer programming (see, e.g., [ Dad19 ] ). Yet, the hardness of \mathrm{GapCRP} is perhaps the least well understood among major lattice problems. In particular, it is not even known that exact \mathrm{GapCRP} in the \ell_{2} norm is \mathsf{NP} -hard, even though it is plausibly \mathsf{NP} -hard to approximate within any constant \gamma\geq 1 and \Pi_{2} -hard to approximate to within a small constant \gamma>1 . This stands in contrast to, e.g., the decisional Shortest Vector Problem ( \gamma - \mathrm{GapSVP} ), which a long line of elegant work [ Ajt98 , Mic98 , Kho03 , Kho04 , RR06 , HR07 , Mic12 ] showed to be \mathsf{NP} -hard in any \ell_{p} norm for any constant \gamma\geq 1 . 1 1 1 Formally, this \mathsf{NP} -hardness is only known under randomized reductions , although several works—some of which are very recent [ HS25a , HS25b ] !—have derandomized the reductions in some cases. Seminal work of Haviv and Regev [ HR06 ] was the first—and prior to this work, only—to study the hardness of \mathrm{GapCRP} . (Other work has studied the complexity of \mathrm{GapCRP} more generally, including limitations on its hardness [ GMR04 , Mag20 ] . See Section 1.2 .) Let \gamma - \mathrm{GapCRP}_{p} be \gamma -approximate \mathrm{GapCRP} in the \ell_{p} norm. Haviv and Regev [ HR06 ] showed that for any constant \varepsilon>0 , (3/2-\varepsilon) - \mathrm{GapCRP}_{\infty} is \Pi_{2} -hard, and that for all sufficiently large p there exists \gamma=\gamma(p)>1 such that \gamma - \mathrm{GapCRP}_{p} is \Pi_{2} -hard. However, the cutoff for “sufficiently large” in their work is non-explicit and presumably quite high, and so in some sense not much more is known about the hardness of \mathrm{GapCRP}_{p} for any explicit, finite p than for p=2 . 1.1 Our Results In this work, we address the problem above by showing \mathsf{NP} -hardness of (\gamma-\varepsilon) - \mathrm{GapCRP}_{p} for all p greater than an explicit value p_{0}\approx 35.31 with an explicit approximation factor \gamma=\gamma(p)>1 . This is the first new hardness result for \mathrm{GapCRP} since [ HR06 ] , which was first published 20 years ago. In fact, we show hardness for a new promise variant of \gamma - \mathrm{GapCRP}_{p} called \gamma - \mathrm{BinGapCRP}_{p} where in the YES case every vector in the fundamental parallelepiped \mathcal{P}(\mathbf{B}):=\mathbf{B}\cdot[0,1]^{n} of the input basis \mathbf{B}\in\mathbb{R}^{m\times n} is close in \ell_{p} distance to a lattice vector \mathbf{B}\boldsymbol{x} with a binary coefficient vector \boldsymbol{x}\in\{0,1\}^{n} . (In the NO case, there exists a vector in \mathcal{P}(\mathbf{B}) that is far from every lattice vector \mathbf{B}\boldsymbol{x} for \boldsymbol{x}\in\mathbb{Z}^{n} , as with standard \gamma - \mathrm{GapCRP}_{p} .) \mathrm{BinGapCRP} is reminiscent of the “binary coefficient vector” variant of the Closest Vector Problem often used in hardness reductions (see, e.g., [ GV21 , Definition 7] and [ Ben23 , Definition 3.1] ), and may be of independent interest. It has the YES instances of the Linear Discrepancy Problem ( \mathrm{LinDisc} ) and the NO instances of \mathrm{GapCRP} . It therefore trivially reduces to both problems in any norm in an approximation-preserving way (see Section 2.2 for definitions of these problems). In particular, our result not only implies new hardness for \mathrm{GapCRP}_{p} with p<\infty , but also for \mathrm{LinDisc} in the \ell_{p} norm for p<\infty ( \mathrm{LinDisc} in finite \ell_{p} norms does not seem to have been studied before). Our main result is the following theorem. See also Figure 1 . Theorem 1.1 ( \mathsf{NP} -hardness of approximation for \mathrm{BinGapCRP}_{p} ) . Let \gamma(p):=\Big(\frac{9^{p}+159\cdot 3^{p}}{8^{p+2}+96\cdot 6^{p}}\Big)^{1/p}\ \text{,} (1) and let p_{0}=35.310188\ldots be the unique value of p\geq 1 such that \gamma(p)=1 . Then for all p>p_{0} and any constant \varepsilon>0 , (\gamma(p)-\varepsilon) - \mathrm{BinGapCRP}_{p} is \mathsf{NP} -hard. We note that the expression \gamma(p) in Equation 1 satisfies \lim_{p\to\infty}\gamma(p)=9/8 . Our second result shows how to achieve \Pi_{2} -hardness (rather than just \mathsf{NP} -hardness) of (9/8-\varepsilon) - \mathrm{BinGapCRP} in the \ell_{\infty} norm. Theorem 1.2 ( \Pi_{2} -hardness of approximation for \mathrm{BinGapCRP}_{\infty} ) . For any constant \varepsilon>0 , (9/8-\varepsilon) - \mathrm{BinGapCRP}_{\infty} is \Pi_{2} -hard. Theorem 1.2 is a strengthening of the main result in [ Man21 ] —it shows hardness not just of (9/8-\varepsilon) - \mathrm{LinDisc}_{\infty} but of (9/8-\varepsilon) - \mathrm{BinGapCRP}_{\infty} , where \mathrm{LinDisc}_{\infty} is the Linear Discrepancy Problem in the \ell_{\infty} norm. Theorem 1.2 also gives an alternative proof of \Pi_{2} -hardness of approximation for \gamma - \mathrm{GapCRP}_{\infty} , albeit with a smaller approximation factor than the one achieved by [ HR06 ] . 1.2 Related Work Early work of McLoughlin [ McL84 ] showed that the Covering Radius Problem on error-correcting codes is \Pi_{2} -hard by a reduction from a \Pi_{2} -hard variant of the 3 -Dimensional Matching Problem, which is in turn shown to be \Pi_{2} -hard by a reduction from \Pi_{2} - 3 -SAT. 2 2 2 Here and throughout this section we refer to linear error-correcting codes simply as “codes.” Twenty years later, work of Guruswami, Micciancio, and Regev [ GMR04 ] studied the complexity of the Covering Radius Problem both on codes and lattices. It showed a number of results, including that the Covering Radius Problem on codes is \mathsf{NP} -hard to approximate to within any constant and \Pi_{2} -hard to approximate to within some constant. (It did not show hardness results for \mathrm{GapCRP} on lattices.) The work [ GMR04 ] also showed that 2 - \mathrm{GapCRP}_{p} for any p is in \mathsf{AM} via an elegant protocol. The fact that 2 - \mathrm{GapCRP}_{p} is in \mathsf{AM} provides evidence that \gamma - \mathrm{GapCRP}_{p} for \gamma\geq 2 is unlikely to be \Pi_{2} -hard, since if it were the polynomial hierarchy would collapse. However, being in \mathsf{AM} says nothing about the potential \mathsf{NP} -hardness of these problems. In particular it could very well be the case that \gamma - \mathrm{GapCRP} is \mathsf{NP} -hard for every constant \gamma\geq 1 as is the case for the Covering Radius Problem on codes. The factor of \gamma=2 in the [ GMR04 ] \mathsf{AM} protocol follows generically for \mathrm{GapCRP} in any norm from the triangle inequality, but it is not always tight. Follow-up work by Haviv, Lyubashevsky, and Regev [ HLR09 ] studied the distribution of the (normalized) \ell_{p} distance of a random point in a fundamental domain of a lattice to the lattice. This distribution is closely related to the [ GMR04 ] \mathsf{AM} protocol, and [ HLR09 ] showed that \gamma - \mathrm{GapCRP}_{2} for \gamma>\sqrt{3}\approx 1.732 is in \mathsf{AM} under a certain conjecture about this distribution in the \ell_{2} norm. Their conjecture was subsequently proved by Magazinov [ Mag20 ] . Understanding the worst-case hardness of \gamma - \mathrm{GapCRP} is also motivated by its relevance to cryptography. Indeed, [ Mic02 ] showed that \gamma - \mathrm{GapCRP} with sufficiently large polynomial \gamma=\gamma(n) can be taken as the starting worst-case problem for a worst-case to average-case reduction to the problems used as the foundation of lattice-based cryptography. The Haviv-Regev hardness reduction. The work of Haviv and Regev [ HR06 ] is the only prior work that studied the worst-case hardness of \mathrm{GapCRP} on lattices. As noted above, they showed that for every constant \varepsilon>0 , (3/2-\varepsilon) - \mathrm{GapCRP}_{\infty} is \Pi_{2} -hard and that for all sufficiently large p there exists \gamma=\gamma(p) such that \gamma - \mathrm{GapCRP}_{p} is \Pi_{2} -hard to approximate. However, the cutoff for “sufficiently large” and the approximation factors \gamma(p) for p<\infty are non-explicit. The reduction in [ HR06 ] is from the Group Coloring Problem on graphs with respect to the group \mathbb{Z}_{3} , a problem that is \Pi_{2} -hard. 3 3 3 Their reduction actually works with \mathbb{Z}_{q} for any q\geq 3 , but they achieve the best hardness of approximation with q=3 . The problem is defined as follows. The input is a directed graph G=(V,E) . The goal is to decide whether for every assignment \phi:E\to\mathbb{Z}_{3} of labels to edges, there exists a coloring c:V\to\mathbb{Z}_{3} of vertices such that for every edge e=(u,v)\in E , c(u)-c(v)\neq\phi(e) . The reduction to \mathrm{GapCRP} is as follows. Let A=A(G)\in\mathbb{Z}^{m\times n} for m:=|E| , n:=|V| be the incidence matrix of G . That is, A is the matrix with two non-zero entries per row defined as A_{i,j}:=\begin{cases}-1&\text{if edge $e_{i}=(v_{j},u)$ for some $u\in V$,}\\ 1&\text{if edge $e_{i}=(u,v_{j})$ for some $u\in V$,}\\ 0&\text{otherwise.}\end{cases} The reduction then outputs (a basis of) the lattice \mathcal{L}:=A\cdot\mathbb{Z}^{n}+3\mathbb{Z}^{m} . One may also view A as the generator matrix of a ternary code \mathcal{C}\subseteq\mathbb{F}_{3}^{m} , and \mathcal{L} as the Construction-A lattice \mathcal{C}+3\mathbb{Z}^{m} . To show \mathsf{NP} -hardness of \gamma - \mathrm{GapCRP}_{p} in some \ell_{p} norm (for large \gamma ), one might try to reduce from variants of the 3 -Coloring Problem, which is the \mathsf{NP} analog of the \Pi_{2} -complete \mathbb{Z}_{3} -Group Coloring Problem. Indeed, strong hardness of approximation results are known for Almost- 3 -Coloring—the optimization variant of 3 -Coloring in which the goal is to minimize the number of monochromatic edges—assuming variants of the Unique Games Conjecture [ DMR06 ] . However, although an analog of the soundness argument in [ HR06 ] holds for (Almost-) 3 -Coloring, it is unclear how to show an analog of the completeness argument. Combinatorial and linear discrepancy. The (combinatorial) discrepancy of a set system S_{1},\ldots,S_{m}\subseteq\{x_{1},\ldots,x_{n}\} is defined as \min_{x_{1},\ldots,x_{n}\in\{-1,1\}}\max_{i\in[m]}|\sum_{j\in S_{i}}x_{j}| , and the goal of the combinatorial discrepancy problem is, given the set system as input, to find x_{1},\ldots,x_{n}\in\{-1,1\} that achieve this minimum. Equivalently, if \mathbf{A}\in\{0,1\}^{m\times n} is the incidence matrix of the input set system, the goal is to find \boldsymbol{x}\in\{-1,1\}^{n} that minimizes \lVert\mathbf{A}\boldsymbol{x}\rVert_{\infty} . Combinatorial discrepancy and other variants of discrepancy are used widely in computer science and math (see, e.g., [ CST14 ] ). Linear discrepancy was originally defined and related to other notions of discrepancy in work of Lovász, Spencer, and Vestergombi [ LSV86 ] , and it appears as a key ingredient in certain approximation algorithms (see, e.g., [ EPR13 , Rot16 , HR17 ] ). Formally, we define the linear discrepancy \lindisc(\mathbf{B}) of a matrix \mathbf{B} in the \ell_{p} norm as 4 4 4 “Standard” linear discrepancy corresponds to \lindisc_{\infty} , and, to the best of our knowledge, our work is the first to extend the definition to finite \ell_{p} norms. This extension is useful for our work. \lindisc_{p}(\mathbf{B}):=\max_{\boldsymbol{w}\in[0,1]^{n}}\min_{\boldsymbol{x}\in\{0,1\}^{n}}\lVert\mathbf{B}(\boldsymbol{w}-\boldsymbol{x})\rVert_{p}\ \text{.} (2) This definition is syntactically very similar to the definition of the covering radius in the \ell_{p} norm, \mu_{p} . The difference is that in the definition of \mu_{p} , the minimum is taken over \boldsymbol{x}\in\mathbb{Z}^{n} rather than \boldsymbol{x}\in\{0,1\}^{n} . See Sections 2.1 and 2.2 . Combinatorial discrepancy is captured, up to translation and scaling, by fixing \boldsymbol{w}:=\frac{1}{2}\cdot\boldsymbol{1} in Equation 2 instead of taking the max over all \boldsymbol{w}\in[0,1]^{n} there. Linear discrepancy was first investigated from a complexity perspective by Li and Nikolov [ LN20 ] , who provided both algorithms and hardness results. In particular, they showed that the exact Linear Discrepancy Problem in the \ell_{\infty} norm, \mathrm{LinDisc}_{\infty} , is \mathsf{NP} -hard and that it is contained in \Pi_{2} . Their hardness result was subsequently improved by Manurangsi [ Man21 ] , who showed that \gamma - \mathrm{LinDisc}_{\infty} is \Pi_{2} -hard for \gamma:=9/8-\varepsilon for any constant \varepsilon>0 . Our work makes extensive use of [ Man21 ] . 1.3 Technical Overview At a high level, our hardness reduction for \mathrm{BinGapCRP}_{p} follows the hardness reduction for \mathrm{LinDisc}_{\infty} in [ Man21 ] . The reduction in [ Man21 ] reduces from NAE - 3 - SAT , the constraint satisfaction problem in which each constraint is a function of three literals (Boolean variables v_{j} or their negations \lnot v_{j} ), and a constraint is satisfied by an assignment to its variables if and only if the assignment neither satisfies none of its literals nor all of its literals. Specifically, on input a NAE - 3 - SAT formula \phi(v_{1},\ldots,v_{n}) with n Boolean variables and with m constraints, the \mathsf{NP} -hardness reduction in [ Man21 ] first computes the constraint-variable incidence matrix \mathbf{B}=\mathbf{B}(\phi)\in\mathbb{Z}^{m\times n} with entries 5 5 5 In fact, [ Man21 ] reduces from the NAE - 3 - SAT (rather than NAE - E 3 - SAT ) problem, in which constraints may have two literals rather than three. The reduction simply doubles an arbitrary literal in any constraint with two literals, which leads to a matrix \mathbf{B} potentially containing entries from \{-2,2\} as well as \{-1,0,1\} . In this work, we reduce from NAE - E 3 - SAT . B_{i,j}:=\begin{cases}1&\text{if constraint $i$ contains $v_{j}$ ,}\\ -1&\text{if constraint $i$ contains $\lnot v_{j}$ ,}\\ 0&\text{otherwise .}\end{cases} It then outputs a \mathrm{LinDisc}_{\infty} instance with matrix \mathbf{A}:=\begin{pmatrix}\frac{1}{3}\mathbf{B}&\frac{1}{3}\mathbf{B}&\frac{1}{3}\mathbf{B}\\ &\mathbf{G}\otimes\mathbf{I}_{n}\end{pmatrix}\in\mathbb{Q}^{(m+3n)\times 3n}\ \text{,} (3) where \mathbf{G} is the 3\times 3 gadget matrix \mathbf{G}:=\begin{pmatrix}1&1&-1\\ 1&-1&1\\ -1&1&1\end{pmatrix}\ \text{,} \otimes is the Kronecker product and \mathbf{I}_{n} is the n\times n identity matrix. Both the completeness and soundness analysis of the reduction in [ Man21 ] crucially use properties of \mathbf{G} . For example, [ Man21 , Lemma 3] argues that \mathbf{G} has low discrepancy by upper bounding the distance between \mathbf{G}\boldsymbol{u} and \mathbf{G}\cdot\{0,1\}^{3} for each \boldsymbol{u}\in[0,1]^{3} via a case analysis on the \ell_{1} norm of \boldsymbol{u} . The soundness analysis shows that, if there exists a close vector in the set \mathbf{A}\cdot\{0,1\}^{3n} to \mathbf{A}\cdot(\frac{1}{2}\boldsymbol{1}) , then \phi must be satisfiable. [ Man21 ] also shows \Pi_{2} -hardness of (9/8-\varepsilon) - \mathrm{LinDisc}_{\infty} by outputting and analyzing a matrix \mathbf{A}^{\prime}=\mathbf{A}^{\prime}(\phi) defined in terms of \phi that is related to the matrix \mathbf{A} defined in Equation 3 but more complicated. We use this same matrix \mathbf{A}^{\prime} (defined in Equation 26 ) to prove Theorem 1.2 . At a technical level, our \mathsf{NP} -hardness result adapts the machinery in [ Man21 ] from \ell_{\infty} to general \ell_{p} norms, and shows that, if the NAE - E 3 - SAT formula \phi is unsatisfiable, then not only is \lindisc(\mathbf{A}) large, in fact \mu(\mathcal{L}(\mathbf{A})) is large. That is, we show that if \phi is unsatisfiable then there exists \boldsymbol{w}\in[0,1]^{3n} (in fact, \boldsymbol{w}:=\frac{1}{2}\cdot\boldsymbol{1} ) such that \lVert\mathbf{A}(\boldsymbol{w}-\boldsymbol{x})\rVert_{p} is large not only for all \boldsymbol{x}\in\{0,1\}^{3n} but for all \boldsymbol{x}\in\mathbb{Z}^{3n} . Doing these things requires making a number of modifications to the hardness reduction and analysis used by [ Man21 ] , such as 1. Using hardness of approximation for NAE - E 3 - SAT with soundness 15/16+\varepsilon and perfect completeness; see Theorem 2.8 . Although this result is likely folklore, we did not find a suitable reference for it and give a proof in Appendix A . 2. Taking the Kronecker product of G with the “ \ell_{p} norm degree” diagonal matrix \mathbf{D}_{p}:=\mathbf{D}_{p}(\phi)=\diag(\deg(v_{1})^{1/p},\ldots,\deg(v_{n})^{1/p})\in\mathbb{R}^{n\times n} in the definition of \mathbf{A} instead of just taking the Kronecker product with I_{n} . Here \deg(v_{i}) counts the number of occurrences of the variable v_{i} and its negation \lnot v_{i} in the formula \phi . 3. Extending the analysis from [ Man21 ] for the gadget matrix \mathbf{G} . For example, we prove an \ell_{p} analog of the fact that \lindisc(\mathbf{G})_{\infty} is small (and in fact, that something stronger is true) in Lemma 3.1 , and we observe that \mathbf{G}\cdot\boldsymbol{0}=\boldsymbol{0} and \mathbf{G}\cdot\boldsymbol{1}=\boldsymbol{1} are the only closest vectors in \mathcal{L}(\mathbf{G})=\mathbf{G}\cdot\mathbb{Z}^{3} to \mathbf{G}\cdot(\frac{1}{2}\boldsymbol{1}) (and not just the only closest vectors in \mathbf{G}\cdot\{0,1\}^{3} to \mathbf{G}\cdot(\frac{1}{2}\boldsymbol{1}) ) in Lemma 3.2 . For Item 1 , we note that the soundness-to-completeness ratio of 15/16 in Theorem 2.8 is not tight. In fact, recent work of Brakensiek, Huang, Potechin, and Zwick [ BHPZ25 ] shows tight upper and lower bounds for NAE - E 3 - SAT with a lower (i.e., better) soundness-to-completeness ratio of roughly 0.9089<15/16=0.9375 . However, Theorem 2.8 shows hardness of (\delta,\varepsilon) - NAE - E 3 - SAT with perfect completeness (i.e., with \varepsilon=1 ), whereas the result of [ BHPZ25 ] does not. This is important since our main hardness reduction for \mathrm{BinGapCRP}_{p} requires reducing from (\delta,\varepsilon) - NAE - E 3 - SAT with nearly perfect completeness. 1.4 Open Questions We again emphasize the central open question that we consider in this work: For which values of \gamma=\gamma(p) is \gamma - \mathrm{GapCRP} in the \ell_{p} norm \mathsf{NP} -hard, and for which is it \Pi_{2} -hard? In particular, we reiterate that the problem of showing \mathsf{NP} -hardness of exact \mathrm{GapCRP} in the \ell_{2} norm (the most important special case) remains open. We again note that the \mathsf{AM} protocol of [ GMR04 ] for approximate \mathrm{GapCRP} (conditionally) rules out \Pi_{2} -hardness for \gamma - \mathrm{GapCRP}_{p} for \gamma\geq 2 , but says nothing about \mathsf{NP} -hardness of \gamma - \mathrm{GapCRP}_{p} . Manurangsi [ Man21 ] notes that no such analogous \mathsf{AM} protocol is known for \mathrm{LinDisc} , and asks if one exists. 1.5 Acknowledgements We thank Ishay Haviv, Pasin Manurangsi, Daniele Micciancio, and Noah Stephens-Davidowitz for helpful comments and references. 2 Preliminaries We will use boldface, lowercase letters to denote vectors. We will sometimes abuse notation when defining column vectors in terms of other column vectors by writing things like \boldsymbol{x}:=(\boldsymbol{y},\boldsymbol{z}) to mean \boldsymbol{x}:=(\boldsymbol{y}^{T},\boldsymbol{z}^{T})^{T} . We will use \boldsymbol{0} and \boldsymbol{1} to denote the all- 0 s and all- 1 s vectors, respectively. We define the predicate \mathrm{sgndiff}(\boldsymbol{x},\boldsymbol{y}) on vectors \boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{n} to be true if and only if the Hadamard (entry-wise) product \boldsymbol{x}\odot\boldsymbol{y}\in\mathbb{R}^{n} has at least one non-positive coordinate and at least one non-negative coordinate. We will use the simple fact that if \mathrm{sgndiff}(\boldsymbol{x},\boldsymbol{y}) holds and if \max_{i}|x_{i}y_{i}|\leq r for some r\geq 0 , then |\langle\boldsymbol{x},\boldsymbol{y}\rangle|=|\sum_{i=1}^{n}x_{i}y_{i}|\leq r(n-1) . 2.1 Covering Radius and Linear Discrepancy We call a matrix \mathbf{B}=(\boldsymbol{b}_{1},\ldots,\boldsymbol{b}_{n})\in\mathbb{R}^{m\times n} with full column rank a basis . In particular, m\geq n for a basis. The lattice \mathcal{L}(\mathbf{B}) generated by \mathbf{B} is defined as \mathcal{L}(\mathbf{B}):=\big\{\sum_{i=1}^{n}a_{i}\boldsymbol{b}_{i}:a_{1},\ldots,a_{n}\in\mathbb{Z}\big\}\ \text{.} For p\geq 1 , the \ell_{p} covering radius of a lattice \mathcal{L}\subset\mathbb{R}^{m} is defined as \mu_{p}(\mathcal{L}):=\max_{\boldsymbol{t}\in\lspan(\mathcal{L})}\mathrm{dist}_{p}(\boldsymbol{t},\mathcal{L})\ \text{,} where for a discrete set S , we define \mathrm{dist}_{p}(\boldsymbol{t},S):=\min_{\boldsymbol{y}\in S}\lVert\boldsymbol{t}-\boldsymbol{y}\rVert_{p} . Because \mathrm{dist}_{p}(\boldsymbol{t}+\boldsymbol{y},\mathcal{L})=\mathrm{dist}_{p}(\boldsymbol{t},\mathcal{L}) for any \boldsymbol{t}\in\mathbb{R}^{m} and \boldsymbol{y}\in\mathcal{L} , we have that if \mathcal{L}=\mathcal{L}(\mathbf{B}) for a basis \mathbf{B}\in\mathbb{R}^{m\times n} , \mu_{p}(\mathcal{L})=\max_{\boldsymbol{w}\in\mathbb{R}^{n}}\min_{\boldsymbol{x}\in\mathbb{Z}^{n}}\lVert\mathbf{B}(\boldsymbol{w}-\boldsymbol{x})\rVert_{p}=\max_{\boldsymbol{w}\in[0,1]^{n}}\min_{\boldsymbol{x}\in\mathbb{Z}^{n}}\lVert\mathbf{B}(\boldsymbol{w}-\boldsymbol{x})\rVert_{p}\ \text{.} (4) That is, because the distance of a vector \mathbf{B}\boldsymbol{w} to \mathcal{L}(\mathbf{B}) is invariant under shifts by lattice vectors (i.e., vectors \mathbf{B}\boldsymbol{x} for \boldsymbol{x}\in\mathbb{Z}^{n} ), it suffices to consider the maximum distance of vectors \mathbf{B}\boldsymbol{w} in the fundamental parallelepiped \mathcal{P}(\mathbf{B}):=\mathbf{B}\cdot[0,1]^{n} to the lattice. We will also work with linear discrepancy , a quantity closely related to the covering radius that was first defined in [ LSV86 ] . For p\geq 1 , the linear discrepancy \lindisc(\mathbf{B}) of a matrix \mathbf{B} is defined as 6 6 6 The definition of \lindisc(\mathbf{B}) does not require \mathbf{B} to be a basis. I.e., \mathbf{B} is allowed to have linearly dependent columns. \lindisc_{p}(\mathbf{B}):=\max_{\boldsymbol{w}\in[0,1]^{n}}\min_{\boldsymbol{x}\in\{0,1\}^{n}}\lVert\mathbf{B}(\boldsymbol{w}-\boldsymbol{x})\rVert_{p}\ \text{.} (5) Covering radius versus linear discrepancy. We note that the equivalent formulation of \mu_{p}(\mathcal{L}) on the right-hand side of Equation 4 and the definition of \lindisc(\mathbf{B}) are syntactically very similar. The only difference is that the minimum in Equation 4 is taken over \boldsymbol{x}\in\mathbb{Z}^{n} (which corresponds to the entire lattice \mathcal{L}(\mathbf{B})=\{\mathbf{B}\boldsymbol{x}:\boldsymbol{x}\in\mathbb{Z}^{n}\} ) whereas in Equation 5 the minimum is only taken over \boldsymbol{x}\in\{0,1\}^{n} (which corresponds to binary linear combinations \mathbf{B}\boldsymbol{x} of basis vectors). Despite the similarity of the definitions of \mu_{p} and \lindisc_{p} , we emphasize that they capture different quantities. In particular, the closest vector in the lattice \mathcal{L}(\mathbf{B}):=\mathbf{B}\cdot\mathbb{Z}^{n} to a vector \mathbf{B}\cdot\boldsymbol{w} for \boldsymbol{w}\in[0,1]^{n} need not be a vector in \mathbf{B}\cdot\{0,1\}^{n} . We give a simple example of this for the lattice \mathbb{Z}^{2} when the input basis \mathbf{B} consists of rather long vectors. Example 2.1 . Consider the basis \mathbf{B}:=\begin{pmatrix}3&4\\ 1&1\end{pmatrix}\ \text{,} and note that \mathcal{L}(\mathbf{B})=\mathbb{Z}^{2} since \det(\mathbf{B})=-1 (i.e., \mathbf{B} is unimodular). Let \boldsymbol{w}:=(1,1/2)^{T} , and note that \mathbf{B}\boldsymbol{w}=(5,3/2)^{T} . Then \mathrm{dist}_{p}(\mathbf{B}\boldsymbol{w},\mathcal{L}(\mathbf{B}))=\mathrm{dist}_{p}(\mathbf{B}\boldsymbol{w},\mathbb{Z}^{2})=\lVert\mathbf{B}((3,-1)^{T}-\boldsymbol{w})\rVert_{p}=1/2\ \text{,} but one can check that \lVert\mathbf{B}(\boldsymbol{x}-\boldsymbol{w})\rVert_{p}>1/2 for all \boldsymbol{x}\in\{0,1\}^{2} . 2.2 Covering Radius and Linear Discrepancy as Computational Problems We next define the approximate decisional Covering Radius Problem in the \ell_{p} norm, \gamma - \mathrm{GapCRP} , and the closely related approximate Linear Discrepancy Problem in the \ell_{p} norm, \gamma - \mathrm{LinDisc}_{p} . Definition 2.2 . Let p\in[1,\infty] and let \gamma=\gamma(n)\geq 1 . The \gamma -approximate decisional Covering Radius Problem in the \ell_{p} norm ( \gamma - \mathrm{GapCRP}_{p} ), is the problem where, on input a basis \mathbf{B}\in\mathbb{Q}^{m\times n} and a value r>0 , the goal is to distinguish between the following two cases. • (YES instance.) \mu_{p}(\mathcal{L}(\mathbf{B}))\leq r . • (NO instance.) \mu_{p}(\mathcal{L}(\mathbf{B}))>\gamma r . Definition 2.3 . Let p\in[1,\infty] and let \gamma=\gamma(n)\geq 1 . The \gamma -approximate decisional Linear Disrepancy Problem in the \ell_{p} norm ( \gamma - \mathrm{LinDisc}_{p} ) is the problem where, on input a basis \mathbf{B}\in\mathbb{Q}^{m\times n} and a value r>0 , the goal is to distinguish between the following two cases. • (YES instance.) \lindisc_{p}(\mathbf{B})\leq r . • (NO instance.) \lindisc_{p}(\mathbf{B})>\gamma r . Finally, we define the binary decisional Covering Radius Problem \mathrm{BinGapCRP} , which has the YES instances of \mathrm{LinDisc} and the NO instances of \mathrm{GapCRP} . Definition 2.4 . Let p\in[1,\infty] and let \gamma=\gamma(n)\geq 1 . The \gamma -approximate decisional Binary Covering Radius Problem in the \ell_{p} norm ( \gamma - \mathrm{BinGapCRP}_{p} ) is the problem where, on input a basis \mathbf{B}\in\mathbb{Q}^{m\times n} and a value r>0 , the goal is to distinguish between the following two cases. • (YES instance.) \lindisc_{p}(\mathbf{B})\leq r . • (NO instance.) \mu_{p}(\mathcal{L}(\mathbf{B}))>\gamma r . We note that \mu_{p}(\mathcal{L}(\mathbf{B}))\leq\lindisc_{p}(\mathbf{B}) for any p\in[1,\infty] and any basis \mathbf{B} . Therefore, for any p\in[1,\infty] and \gamma\geq 1 , YES (respectively, NO) instances of \gamma - \mathrm{BinGapCRP}_{p} are YES (respectively, NO) instances of both \gamma - \mathrm{GapCRP}_{p} and \gamma - \mathrm{LinDisc}_{p} . We therefore immediately have the following observation. Fact 2.5 . For any \gamma\geq 1 and p\in[1,\infty] , the identity mapping (\mathbf{B},r)\mapsto(\mathbf{B},r) is a (polynomial-time) reduction from \gamma - \mathrm{BinGapCRP}_{p} to \gamma - \mathrm{GapCRP}_{p} and to \gamma - \mathrm{LinDisc}_{p} . 2.3 Constraint Satisfaction Problems A (Boolean) constraint satisfaction problem (CSP) is defined by a set of Boolean variables X=\{x_{1},\dots,x_{n}\} , and a set of functions called constraints \mathcal{C}=\{C_{1},\dots,C_{m}\} with C_{i}\colon\{0,1\}^{|C_{i}|}\to\{0,1\} . An assignment of the variables is a map from X\to\{0,1\} . A constraint C_{i} is satisfied by an assignment if the output of the constraint on the assignment of the variables is 1 . Let \phi be a CSP and let \psi be an assignment of the variables in \phi . We define \mathrm{val}_{\psi}(\phi) to be the fraction of constraints in \phi satisfied by an assignment \psi , and define the value of \phi to be \mathrm{val}(\phi):=\max_{\psi}\mathrm{val}_{\psi}(\phi) . We then define the computational problem (\delta,\varepsilon) - \mathrm{CSP} as follows. Definition 2.6 (Constraint Satisfaction Problems (CSP)) . For \delta,\varepsilon\in\mathbb{R} be such that 0<\delta\leq\varepsilon\leq 1 , (\delta,\varepsilon) - \mathrm{CSP} is the decision problem defined as follows. On input a collection of constraints \mathcal{C}=\{C_{1},\ldots,C_{m}\} , the goal is to decide between the follows two cases. • (YES instance.) \mathrm{val}(\phi)\geq\varepsilon . • (NO instance.) \mathrm{val}(\phi)<\delta . We now introduce NAE - E k - SAT , a k -ary CSP that will be important for our hardness reductions. Definition 2.7 ( (\delta,\varepsilon) - NAE - E k - SAT problem) . A NAE - E k - SAT formula \phi consists of n Boolean variables X=\{x_{1},\ldots,x_{n}\} and m constraints C_{1},\ldots,C_{m} , where each constraint C_{i} is a function of exactly k distinct literals (Boolean variables x_{j} or their negations \lnot x_{j} ). A constraint C_{i} is satisfied by an assignment if and only if not all k of its literals evaluate either to 1 or to 0 . Let \delta,\varepsilon\in\mathbb{R} be such that 0<\delta\leq\varepsilon\leq 1 . The goal of the (\delta,\varepsilon) - NAE - E k - SAT problem is, given a NAE - E k - SAT formula as input, to decide between the following two cases. • (YES instance.) \mathrm{val}(\phi)\geq\varepsilon . • (NO instance.) \mathrm{val}(\phi)<\delta . We represent NAE - E k - SAT constraints C as sets of k literals, and we use the notation \mathrm{vars}(C) to denote the set of indices of variables involved in a NAE - E 3 - SAT constraint C . For example, if k=3 and C:=\{v_{1},\lnot v_{3},\lnot v_{4}\} then \mathrm{vars}(C)=\{1,3,4\} . We define \textrm{sgn}(\ell)\in\{-1,1\} and \mathrm{var}(\ell) to be the sign and the index of the variable underlying a literal \ell , respectively. For example, \textrm{sgn}(\lnot v_{4})=-1 and \mathrm{var}(\lnot v_{4})=4 . We next give a result showing \mathsf{NP} -hardness of (15/16+\varepsilon,1) - NAE - E 3 - SAT for any constant \varepsilon>0 in Theorem 2.8 . This result follows by combining a tight hardness of approximation result for NAE - E 4 - SAT by Håstad [ Hs01 ] ( Theorem A.1 ) with a reduction from approximate NAE - E 4 - SAT to approximate NAE - E 3 - SAT ( Theorem A.3 ). While Theorem 2.8 may very well be folklore, we did not find a suitable reference for it and so include its proof in Appendix A . Theorem 2.8 . For any constant \varepsilon\in(0,1/16) , (15/16+\varepsilon,1) - NAE - E 3 - SAT is \mathsf{NP} -hard. 3 Reduction from NAE3SAT to BinaryGapCRP 3.1 The Reduction We start by giving our reduction from (\delta,\varepsilon) - NAE - E 3 - SAT to \gamma - \mathrm{BinGapCRP}_{p} for certain values of \delta,\varepsilon,\gamma,p . In what follows, we will analyze the reduction and for which parameter values it is valid. We emphasize again that the reduction is similar to the \mathsf{NP} -hardness reduction in [ Man21 ] for \mathrm{LinDisc}_{\infty} . Let \phi be the input (\delta,\varepsilon) - NAE - E 3 - SAT formula, and assume that \phi has n variables v_{1},\dots,v_{n} and m constraints C_{1},\dots,C_{m} . We define the incidence matrix \mathbf{B}\in\mathbb{R}^{m\times n} of \phi as B_{i,j}:=B_{i,j}(\phi)=\begin{cases}1&\text{if constraint $C_{i}$ contains literal $v_{j}$ ,}\\ -1&\text{if constraint $C_{i}$ contains literal $\lnot v_{j}$ ,}\\ 0&\text{otherwise .}\end{cases} (6) We will also use the following gadget matrix, defined in [ Man21 ] , which we analyze in Section 3.2 . \mathbf{G}:=\begin{pmatrix}1&1&-1\\ 1&-1&1\\ -1&1&1\end{pmatrix}\ \text{.} (7) Let \deg_{\phi}(v_{j}) denote the number of constraints C_{i} in \phi containing either v_{j} or \lnot v_{j} . When the formula \phi is clear from context, we simply write \deg(v_{j}) . For p\in[1,\infty] , define the diagonal matrix \mathbf{D}_{p}:=\mathbf{D}_{p}(\phi)=\diag(\deg(v_{1})^{1/p},\ldots,\deg(v_{n})^{1/p})=\begin{pmatrix}\deg(v_{1})^{1/p}&\\ &\ddots&\\ &&\deg(v_{n})^{1/p}\end{pmatrix}\in\mathbb{R}^{n\times n}\ \text{.} Finally, we output the \gamma - \mathrm{BinGapCRP}_{p} instance consisting of the matrix \mathbf{A}:=\mathbf{A}_{p}(\phi)=\begin{pmatrix}\frac{1}{3}\mathbf{B}&\frac{1}{3}\mathbf{B}&\frac{1}{3}\mathbf{B}\\ &\mathbf{G}\otimes\mathbf{D}_{p}\end{pmatrix}\in\mathbb{R}^{(m+3n)\times 3n}\ \text{,} (8) and distance threshold r:=(\varepsilon m\cdot(4/3)^{p}+(1-\varepsilon)m\cdot 2^{p}+3m(2+(4/3)^{p}))^{1/p}>0\ \text{.} (9) 3.2 Analysis of the matrix \mathbf{G} We begin by presenting some technical lemmas about \mathbf{G} that will be useful in our hardness reductions. We start with Lemma 3.1 , which adapts [ Man21 , Lemma 3] from the \ell_{\infty} norm to \ell_{p} norms. Lemma 3.1 . For any \boldsymbol{u}\in[0,1]^{3} and b\in\{-1,1\} , there exists \boldsymbol{z}\in\{0,1\}^{3} such that 1. (Low discrepancy w.r.t. \mathbf{G} .) \lVert\mathbf{G}(\boldsymbol{u}-\boldsymbol{z})\rVert_{p}^{p}\leq 2+(4/3)^{p} , where \mathbf{G} is as defined in Equation 7 . 2. (Sign agreement.) b\cdot(\boldsymbol{1}^{T}(\boldsymbol{u}-\boldsymbol{z}))\geq 0 . 3. (Low discrepancy w.r.t. \boldsymbol{1}^{T} .) |\boldsymbol{1}^{T}(\boldsymbol{u}-\boldsymbol{z})|\leq 2 . Proof. The second and third properties are identical to the corresponding properties in [ Man21 , Lemma 3] (which are proved there), and so we only prove the first property. We follow the structure of the proof of [ Man21 , Lemma 3, Item 1] to prove the first property. We assume without loss of generality that 0\leq u_{1}\leq u_{2}\leq u_{3}\leq 1 throughout the proof. This assumption is justified by the easy-to-check fact that for all 3\times 3 permutation matrices \mathbf{P} and \boldsymbol{x}\in\mathbb{R}^{3} , \lVert\mathbf{G}\boldsymbol{x}\rVert_{\infty}=\lVert\mathbf{G}\mathbf{P}\boldsymbol{x}\rVert_{\infty} . We now proceed to the proof of Item 1 . We will consider three cases, and in each case we will bound each coordinate of \mathbf{G}(\boldsymbol{u}-\boldsymbol{z}) individually. Case 1 : \boldsymbol{1}^{T}\boldsymbol{u}\geq 2 . In this case we set \boldsymbol{z}:=(0,1,1)^{T} , and have \mathbf{G}(\boldsymbol{u}-\boldsymbol{z})=\begin{pmatrix}u_{1}+u_{2}-u_{3}\\ u_{1}-u_{2}+u_{3}\\ -u_{1}+u_{2}+u_{3}-2\end{pmatrix}\ \text{.} We have following bounds: • -1\leq-u_{3}\leq(\mathbf{G}(\boldsymbol{u}-\boldsymbol{z}))_{1}=(\mathbf{G}\boldsymbol{u})_{1}\leq u_{1}\leq 1 . • -1\leq-u_{2}\leq(\mathbf{G}(\boldsymbol{u}-\boldsymbol{z}))_{2}=(\mathbf{G}\boldsymbol{u}))_{2}\leq u_{3}\leq 1 . • -4/3\leq u_{3}-2\leq(\mathbf{G}(\boldsymbol{u}-\boldsymbol{z}))_{3}=(\mathbf{G}\boldsymbol{u})_{3}-2\leq-u_{1}\leq 0 . Case 2 : \boldsymbol{1}^{T}\boldsymbol{u}<2 and (\mathbf{G}\boldsymbol{u})_{3}\leq 4/3 . 7 7 7 In fact, the assumption that \boldsymbol{1}^{T}\boldsymbol{u}<2 is not even necessary here. In this case we set \boldsymbol{z}:=\boldsymbol{0} , and have \mathbf{G}(\boldsymbol{u}-\boldsymbol{z})=\begin{pmatrix}u_{1}+u_{2}-u_{3}\\ u_{1}-u_{2}+u_{3}\\ -u_{1}+u_{2}+u_{3}\end{pmatrix}\ \text{.} We have the following bounds: • -1\leq-u_{3}\leq(\mathbf{G}(\boldsymbol{u}-\boldsymbol{z}))_{1}=(\mathbf{G}\boldsymbol{u})_{1}\leq u_{1}\leq 1 . • -1\leq-u_{2}\leq(\mathbf{G}(\boldsymbol{u}-\boldsymbol{z}))_{2}=(\mathbf{G}\boldsymbol{u})_{2}\leq u_{3}\leq 1 . • 0\leq u_{3}\leq(\mathbf{G}(\boldsymbol{u}-\boldsymbol{z}))_{3}=(\mathbf{G}\boldsymbol{u})_{3}\leq 4/3 . Case 3 : \boldsymbol{1}^{T}\boldsymbol{u}<2 and (\mathbf{G}\boldsymbol{u})_{3}>4/3 . In this case we set \boldsymbol{z}:=(0,0,1)^{T} , and have \mathbf{G}(\boldsymbol{u}-\boldsymbol{z})=\begin{pmatrix}u_{1}+u_{2}-u_{3}+1\\ u_{1}-u_{2}+u_{3}-1\\ -u_{1}+u_{2}+u_{3}-1\end{pmatrix}\ \text{.} We have the following bounds: • 0\leq-u_{3}+1\leq(\mathbf{G}(\boldsymbol{u}-\boldsymbol{z}))_{1}=(\mathbf{G}\boldsymbol{u})_{1}+1\leq u_{1}+1=\frac{1}{2}(\boldsymbol{1}^{T}\boldsymbol{u}-(\mathbf{G}\boldsymbol{u})_{3})+1<1/3+1=4/3 . • -1\leq u_{1}-1\leq(\mathbf{G}(\boldsymbol{u}-\boldsymbol{z}))_{2}=(\mathbf{G}\boldsymbol{u})_{2}-1\leq u_{3}-1\leq 0 . • -1\leq u_{3}-1\leq(\mathbf{G}(\boldsymbol{u}-\boldsymbol{z}))_{3}=(\mathbf{G}\boldsymbol{u})_{3}-1\leq\boldsymbol{1}^{T}\boldsymbol{u}-1<1 . In each case, we have \left\lVert\mathbf{G}(\boldsymbol{u}-\boldsymbol{z})\right\rVert^{p}_{p}\leq 2+(4/3)^{p} , as needed. ∎ Lemma 3.2 is the other part of the extension of [ Man21 , Lemma 3] , and facilitates a reduction to \mathrm{BinGapCRP} , rather than just \mathrm{LinDisc} . We both adapt [ Man21 , Lemma 3] to \ell_{p} norms for p<\infty and show that \mathbf{G}(1/2\cdot\boldsymbol{1})=(1/2)\cdot\boldsymbol{1} is far from all vectors in \mathcal{L}(\mathbf{G})\setminus\{\boldsymbol{0},\boldsymbol{1}\}=\mathbf{G}\cdot(\mathbb{Z}^{3}\setminus\{\boldsymbol{0},\boldsymbol{1}\}) rather than just vectors in \mathbf{G}\cdot(\{0,1\}^{3}\setminus\{\boldsymbol{0},\boldsymbol{1}\}) . Lemma 3.2 . Let \boldsymbol{z}\in\mathbb{Z}^{3} and p\in[1,\infty] . Then we have the following: 1. For \boldsymbol{z}\in\{\boldsymbol{0},\boldsymbol{1}\} , \lVert\mathbf{G}(1/2\cdot\boldsymbol{1}-\boldsymbol{z})\rVert^{p}_{p}=3/2^{p} if p<\infty and \lVert\mathbf{G}(1/2\cdot\boldsymbol{1}-\boldsymbol{z})\rVert_{\infty}=1/2 . 2. For \boldsymbol{z}\in\mathbb{Z}^{3}\setminus\{\boldsymbol{0},\boldsymbol{1}\} , \lVert\mathbf{G}(1/2\cdot\boldsymbol{1}-\boldsymbol{z})\rVert^{p}_{p}\geq(2+3^{p})/2^{p} if p<\infty and \lVert\mathbf{G}(1/2\cdot\boldsymbol{1}-\boldsymbol{z})\rVert_{\infty}\geq 3/2 . Proof. We note that \mathbf{G}((1/2)\cdot\boldsymbol{1}-\boldsymbol{z})=(1/2)\cdot\boldsymbol{1}-\mathbf{G}\boldsymbol{z} so that 8 8 8 This is equivalent to the fact that \mathbf{G} has \boldsymbol{1} as an eigenvector with corresponding eigenvalue 1 . \{(\mathbf{G}(1/2\cdot\boldsymbol{1}-\boldsymbol{z}):\boldsymbol{z}\in\mathbb{Z}^{3}\}=\{\mathbf{G}\boldsymbol{z}:\boldsymbol{z}\in\mathbb{Z}^{3}\}+(1/2)\cdot\boldsymbol{1}\subseteq(\mathbb{Z}+1/2)^{3}\ \text{.} That is, for any \boldsymbol{z}\in\mathbb{Z}^{3} , each coordinate of G((1/2\cdot\boldsymbol{1}-\boldsymbol{z}) is contained in \mathbb{Z}+1/2 . Fix such a coefficient vector \boldsymbol{z}\in\mathbb{Z}^{3} . Then for p<\infty , \lVert\mathbf{G}((1/2)\cdot\boldsymbol{1}-\boldsymbol{z})\rVert_{p}^{p}=3/2^{p} if \mathbf{G}\boldsymbol{z}\in\{0,1\}^{3} and \lVert\mathbf{G}((1/2)\cdot\boldsymbol{1}-\boldsymbol{z})\rVert_{p}^{p}\geq(2+3^{p})/2^{p} otherwise. Similarly, \lVert\mathbf{G}((1/2)\cdot\boldsymbol{1}-\boldsymbol{z})\rVert_{\infty}=1/2 if \mathbf{G}\boldsymbol{z}\in\{0,1\}^{3} and \lVert\mathbf{G}((1/2)\cdot\boldsymbol{1}-\boldsymbol{z})\rVert_{\infty}\geq 3/2 otherwise. The lemma then follows by noting that \mathcal{L}(\mathbf{G})\cap\{0,1\}^{3}=\{\boldsymbol{0},\boldsymbol{1}\} . ∎ 3.3 Completeness Analysis We start with an expression for the value of \lVert\mathbf{A}(\boldsymbol{w}-\boldsymbol{x})\rVert_{p}^{p} for the matrix \mathbf{A}=\mathbf{A}(\phi) defined in Equation 8 in terms of a NAE - E 3 - SAT formula \phi and vectors \boldsymbol{w},\boldsymbol{x} . Lemma 3.3 . Let p\geq 1 , and for i\in[3] , let \boldsymbol{y}^{i}\in\mathbb{R}^{n} , let \phi be an NAE - E 3 - SAT formula with constraints C_{1},\dots,C_{m} , and let \mathbf{A}:=\mathbf{A}_{p}(\phi) as defined in Equation 8 . Let \boldsymbol{y}:=(\boldsymbol{y}^{1},\boldsymbol{y}^{2},\boldsymbol{y}^{3})\in\mathbb{R}^{3n} , let \boldsymbol{y}^{\text{sum}}:=\boldsymbol{y}^{1}+\boldsymbol{y}^{2}+\boldsymbol{y}^{3}\in\mathbb{R}^{n} , and for j\in[n] , let \boldsymbol{y}_{j}:=(y^{1}_{j},y^{2}_{j},y^{3}_{j})\in\mathbb{R}^{3} . Then \lVert\mathbf{A}\boldsymbol{y}\rVert_{p}^{p}=(1/3^{p})\cdot\left\lVert\mathbf{B}\boldsymbol{y}^{\text{sum}}\right\rVert_{p}^{p}+\sum_{j=1}^{n}\deg(v_{j})\cdot\left\lVert\mathbf{G}\boldsymbol{y}_{j}\right\rVert_{p}^{p}\ \text{.} (10) Let \boldsymbol{x}^{1},\boldsymbol{x}^{2},\boldsymbol{x}^{3}\in\mathbb{R}^{n} , let \boldsymbol{x}:=(\boldsymbol{x}^{1},\boldsymbol{x}^{2},\boldsymbol{x}^{3})\in\mathbb{R}^{3n} , and let \boldsymbol{x}^{\text{sum}}:=\boldsymbol{x}^{1}+\boldsymbol{x}^{2}+\boldsymbol{x}^{3}\in\mathbb{R}^{n} . Furthermore, for j\in[n] , let \boldsymbol{x}_{j}:=(x^{1}_{j},x^{2}_{j},x^{3}_{j})^{T}\in\mathbb{R}^{3} , and let \boldsymbol{b}_{i} denote the i th row of \mathbf{B} . Then in particular, \left\lVert\mathbf{A}\left(\frac{1}{2}\cdot\boldsymbol{1}-\boldsymbol{x}\right)\right\rVert_{p}^{p}=\sum_{i=1}^{m}\left(\left|\frac{1}{3}\boldsymbol{b}_{i}\left(\frac{3}{2}\cdot\boldsymbol{1}-\boldsymbol{x}^{\text{sum}}\right)\right|^{p}+\sum_{j\in\mathrm{vars}(C_{i})}\left\lVert\mathbf{G}\left(\frac{1}{2}\cdot\boldsymbol{1}-\boldsymbol{x}_{j}\right)\right\rVert_{p}^{p}\right)\ \text{.} (11) Proof. For Equation 10 , \displaystyle\lVert\mathbf{A}(\boldsymbol{y})\rVert_{p}^{p} \displaystyle=\left\lVert(1/3)\cdot(\mathbf{B}\boldsymbol{y}^{1}+\mathbf{B}\boldsymbol{y}^{2}+\mathbf{B}\boldsymbol{y}^{3})\right\rVert_{p}^{p}+\lVert(\mathbf{G}\otimes\mathbf{D}_{p})\cdot\boldsymbol{y}\rVert_{p}^{p} \displaystyle=\left\lVert(1/3)\cdot\mathbf{B}\boldsymbol{y}^{\text{sum}}\right\rVert_{p}^{p}+\sum_{j=1}^{n}\deg(v_{j})\cdot\left\lVert\mathbf{G}\boldsymbol{y}_{j}\right\rVert_{p}^{p}\ \text{.} For Equation 11 , we set \boldsymbol{y}:=\frac{1}{2}\cdot\boldsymbol{1}-\boldsymbol{x} and continue by re-grouping some terms. \displaystyle\left\lVert\mathbf{A}\left(\frac{1}{2}\cdot\boldsymbol{1}-\boldsymbol{x}\right)\right\rVert_{p}^{p} \displaystyle=\frac{1}{3^{p}}\cdot\left\lVert\mathbf{B}\left(\frac{3}{2}\cdot\boldsymbol{1}-\boldsymbol{x}^{\text{sum}}\right)\right\rVert_{p}^{p}+\sum_{j=1}^{n}\deg(v_{j})\cdot\left\lVert\mathbf{G}\left(\frac{1}{2}\cdot\boldsymbol{1}-\boldsymbol{x}_{j}\right)\right\rVert_{p}^{p} \displaystyle=\frac{1}{3^{p}}\cdot\sum_{i=1}^{m}\left|\boldsymbol{b}_{i}\left(\frac{3}{2}\cdot\boldsymbol{1}-\boldsymbol{x}^{\text{sum}}\right)\right|^{p}+\sum_{j=1}^{n}\deg(v_{j})\cdot\left\lVert\mathbf{G}\left(\frac{1}{2}\cdot\boldsymbol{1}-\boldsymbol{x}_{j}\right)\right\rVert_{p}^{p} \displaystyle=\sum_{i=1}^{m}\left(\left|\frac{1}{3}\boldsymbol{b}_{i}\left(\frac{3}{2}\cdot\boldsymbol{1}-\boldsymbol{x}^{\text{sum}}\right)\right|^{p}+\sum_{j\in\mathrm{vars}(C_{i})}\left\lVert\mathbf{G}\left(\frac{1}{2}\cdot\boldsymbol{1}-\boldsymbol{x}_{j}\right)\right\rVert_{p}^{p}\right)\text{.} The first equality follows by setting \boldsymbol{w}:=1/2\cdot\boldsymbol{1} in Equation 10 . The third equality follows by noting for any expression K(j) depending on j , \sum_{j=1}^{n}\deg(v_{j})K(j)=\sum_{j=1}^{n}\sum_{\mathrm{vars}(C_{i}):x_{j}\in\mathrm{vars}(C_{i})}K(j)=\sum_{i=1}^{m}\sum_{j:x_{j}\in\mathrm{vars}(C_{i})}K(j)\ \text{.} Indeed, one can view the two double sums as counting constraint-variable incidences in two different ways. ∎ We now state lemmas that will be used in the proof of Theorem 3.7 . We begin with a lemma for completeness in which we upper bound \lindisc_{p}(\mathbf{A}) . Lemma 3.4 . Let p\in[1,\infty) , let \varepsilon\in[0,1] , let \phi be an NAE - E 3 - SAT instance with m constraints and \mathrm{val}(\phi)\geq\varepsilon , and let \mathbf{A}:=\mathbf{A}_{p}(\phi) be defined as in Equation 8 . Then \lindisc_{p}(\mathbf{A})^{p}\leq(\varepsilon\cdot\left(4/3\right)^{p}+(1-\varepsilon)\cdot 2^{p}+3\left(2+\left(4/3\right)^{p}\right))\cdot m\ \text{.} (12) Proof. Let \psi be an assignment to the variables of \phi such that \mathrm{val}_{\psi}(\phi)\geq\varepsilon . Let \boldsymbol{w}^{1},\boldsymbol{w}^{2},\boldsymbol{w}^{3}\in[0,1]^{n} , and let \boldsymbol{w}:=(\boldsymbol{w}^{1},\boldsymbol{w}^{2},\boldsymbol{w}^{3}) . We define \boldsymbol{x}:=(\boldsymbol{x}^{1},\boldsymbol{x}^{2},\boldsymbol{x}^{3}) for \boldsymbol{x}^{1},\boldsymbol{x}^{2},\boldsymbol{x}^{3}\in\{0,1\}^{n} as follows. For each j\in[n] , the vector \boldsymbol{x}_{j}:=(x^{1}_{j},x^{2}_{j},x^{3}_{j})^{T} is the vector \boldsymbol{z} guaranteed by Lemma 3.1 applied to the vector \boldsymbol{u}:=\boldsymbol{w}_{j}=(w^{1}_{j},w^{2}_{j},w^{3}_{j})^{T} and sign b:=1-2\psi(v_{j}) . We begin by upper bounding \lVert\mathbf{A}(\boldsymbol{w}-\boldsymbol{x})\rVert_{p}^{p} , which we do by upper bounding the terms on the right-hand side of Equation 10 individually with \boldsymbol{y}:=\boldsymbol{w}-\boldsymbol{x}\in\mathbb{R}^{3n} . From Lemma 3.1 , Item 1 and the fact that \phi has total degree \sum_{j=1}^{n}\deg(v_{j})=3m , we have \sum_{j=1}^{n}\deg(v_{j})\cdot\left\lVert\mathbf{G}\left(\boldsymbol{w}_{j}-\boldsymbol{x}_{j}\right)\right\rVert_{p}^{p}\leq\sum_{j=1}^{n}\deg(v_{j})\cdot\left(2+(4/3)^{p}\right)=3m(2+(4/3)^{p})\text{.} (13) To upper bound \left\lVert\frac{1}{3}\mathbf{B}(\boldsymbol{w}^{\text{sum}}-\boldsymbol{x}^{\text{sum}})\right\rVert^{p}_{p} , we upper bound the magnitude of each coordinate i of \mathbf{B}(\boldsymbol{w}^{\text{sum}}-\boldsymbol{x}^{\text{sum}})\in\mathbb{R}^{m} . Suppose that constraint C_{i}=\{\ell_{i,1},\ell_{i,2},\ell_{i,3}\} for some literals \ell_{i,1},\ell_{i,2},\ell_{i,3} . Then (\mathbf{B}(\boldsymbol{w}^{\text{sum}}-\boldsymbol{x}^{\text{sum}}))_{i}=\sum_{j=1}^{3}\textrm{sgn}(\ell_{i,j})\cdot(w_{\mathrm{var}(\ell_{i,j})}^{\text{sum}}-x_{\mathrm{var}(\ell_{i,j})}^{\text{sum}})\ \text{.} (14) By Lemma 3.1 , Item 3 , we have that |\boldsymbol{1}^{T}(\boldsymbol{w}_{j}-\boldsymbol{x}_{j})|=|w^{\text{sum}}_{j}-x^{\text{sum}}_{j}|\leq 2 for all j\in[n] . So, the expression in Equation 14 always has magnitude at most 6 by triangle inequality and has magnitude at most 4 as long as the signs of its summands are not all the same (i.e., as long as \mathrm{sgndiff}(\boldsymbol{b}_{i},\boldsymbol{w}^{\text{sum}}-\boldsymbol{x}^{\text{sum}}) holds, where \boldsymbol{b}_{i} is the i th row of \mathbf{B} ). We show that this is the case if \psi satisfies constraint C_{i} . Assume without loss of generality that w_{\mathrm{var}(\ell_{i,j})}^{\text{sum}}\neq x_{\mathrm{var}(\ell_{i,j})}^{\text{sum}} for j\in[3] (since otherwise the expression clearly has magnitude at most 4 ). By Lemma 3.1 , Item 2 and our choice of the sign 1-2\psi(v_{j}) when applying Lemma 3.1 to \boldsymbol{w}_{j} , we have that for all j\in[n] , (1-2\psi(v_{j}))\cdot(w^{\text{sum}}_{j}-x^{\text{sum}}_{j})\geq 0 , which implies that (1-2\psi(v_{j}))=\textrm{sgn}(w^{\text{sum}}_{j}-x^{\text{sum}}_{j}) . So, for j\in[3] , \textrm{sgn}(\ell_{i,j})\cdot\textrm{sgn}(w_{\mathrm{var}(\ell_{i,j})}^{\text{sum}}-x_{\mathrm{var}(\ell_{i,j})}^{\text{sum}})=\textrm{sgn}(\ell_{i,j})\cdot(1-2\psi(v_{j}))=\begin{cases}-1&\text{if $\psi$ satisfies literal $\ell_{i,j}$ ,}\\ 1&\text{otherwise .}\end{cases} (15) By definition, a NAE - E 3 - SAT constraint C_{i} is satisfied if and only if at least one of its literals is satisfied and at least one is not satisfied. So, if \psi satisfies C_{i} , \textrm{sgn}(\ell_{i,j})\cdot\textrm{sgn}(w_{\mathrm{var}(\ell_{i,j})}^{\text{sum}}-x_{\mathrm{var}(\ell_{i,j})}^{\text{sum}}) is equal to 1 for some j\in[3] and is equal to -1 for some j\in[3] . It follows that the expression in Equation 14 has magnitude at most 4 . Because \mathrm{val}(\phi)\geq\varepsilon by assumption, \lVert(1/3)\cdot\mathbf{B}(\boldsymbol{w}^{\text{sum}}-\boldsymbol{x}^{\text{sum}})\rVert_{p}^{p}\leq\frac{1}{3^{p}}\cdot(\varepsilon m\cdot 4^{p}+(1-\varepsilon)m\cdot 6^{p})=(\varepsilon\cdot(4/3)^{p}+(1-\varepsilon)\cdot 2^{p})\cdot m\ \text{.} (16) Combining the upper bounds of Equations 13 and 16 to the terms in Equation 10 (with \boldsymbol{y}:=\boldsymbol{w}-\boldsymbol{x} ) implies Equation 12 , as needed. ∎ 3.4 Soundness Analysis We now give two lemmas for analyzing the soundness of our reduction. The first lemma establishes that vectors of the form \mathbf{A}\boldsymbol{x} where \boldsymbol{x}\in\{0,1\}^{3n} are closest vectors in \mathcal{L}(\mathbf{A}) to \mathbf{A}\cdot(1/2\cdot\boldsymbol{1}) . Lemma 3.5 . Let p\in[1,\infty] , let \phi be an NAE - E 3 - SAT instance, and let \mathbf{A}:=\mathbf{A}(\phi) be as defined in Equation 8 . Then for every \boldsymbol{y}\in\mathbb{Z}^{3n} , there exists \boldsymbol{x}:=(\boldsymbol{x}^{\prime},\boldsymbol{x}^{\prime},\boldsymbol{x}^{\prime})\in\{0,1\}^{3n} with \boldsymbol{x}^{\prime}\in\{0,1\}^{n} such that \lVert\mathbf{A}(1/2\cdot\boldsymbol{1}-\boldsymbol{x})\rVert_{p}\leq\lVert\mathbf{A}(1/2\cdot\boldsymbol{1}-\boldsymbol{y})\rVert_{p} . Proof. Let \boldsymbol{y}^{1},\boldsymbol{y}^{2},\boldsymbol{y}^{3}\in\mathbb{Z}^{n} be such that \boldsymbol{y}=(\boldsymbol{y}^{1},\boldsymbol{y}^{2},\boldsymbol{y}^{3})\in\mathbb{Z}^{3n} , let \boldsymbol{y}^{\text{sum}}:=\boldsymbol{y}^{1}+\boldsymbol{y}^{2}+\boldsymbol{y}^{3}\in\mathbb{Z}^{n} , and for each j\in[n] , let \boldsymbol{y}_{j}:=(y^{1}_{j},y^{2}_{j},y^{3}_{j}) . For each j\in[n] , define x_{j}^{\prime}:=\begin{cases}0&\text{if $y^{\text{sum}}_{j}\leq 1$ ,}\\ 1&\text{if $y^{\text{sum}}_{j}\geq 2$ .}\end{cases} (17) Furthermore, define \boldsymbol{x}^{\prime}:=(x_{1}^{\prime},\ldots,x_{n}^{\prime})^{T}\in\{0,1\}^{n} , \boldsymbol{x}:=(\boldsymbol{x}^{\prime},\boldsymbol{x}^{\prime},\boldsymbol{x}^{\prime})\in\{0,1\}^{3n} , and for each j\in[n] , \boldsymbol{x}_{j}:=(x^{\prime}_{j},x^{\prime}_{j},x^{\prime}_{j})\in\{0,1\}^{3} . We continue the proof by upper and lower bounding the i th terms in the sum in Equation 11 for \lVert\mathbf{A}(1/2\cdot\boldsymbol{1}-\boldsymbol{x})\rVert^{p}_{p} and for \lVert\mathbf{A}(1/2\cdot\boldsymbol{1}-\boldsymbol{y})\rVert^{p}_{p} , respectively. Specifically, we show that the value of the i th term in the former sum is at most the value of the i th term in the latter sum for every i\in[m] . By the definition of \boldsymbol{x} in terms of \boldsymbol{y} , these i th terms are the same if \boldsymbol{y}_{j}\in\{\boldsymbol{0},\boldsymbol{1}\} for all j\in\mathrm{vars}(C_{i}) , where C_{i} is the i th constraint of \phi . So, we assume without loss of generality that this is not the case, i.e., that for every i\in[m] there exists j\in\mathrm{var}(C_{i}) such that \boldsymbol{y}_{j}\in\mathbb{Z}^{3}\setminus\{\boldsymbol{0},\boldsymbol{1}\} . We begin by upper bounding the terms in \lVert\mathbf{A}(1/2\cdot\boldsymbol{1}-\boldsymbol{x})\rVert^{p}_{p} . Fix some i\in[m] corresponding to a term of Equation 11 . Because \boldsymbol{x}_{j}\in\{\boldsymbol{0},\boldsymbol{1}\} for all j\in[n] by definition, by Lemma 3.2 , we have the equality \sum_{j\in\mathrm{vars}(C_{i})}\lVert\mathbf{G}(1/2\cdot\boldsymbol{1}-\boldsymbol{x}_{j})\rVert^{p}_{p}=\sum_{j\in\mathrm{vars}(C_{i})}3/2^{p}=3\cdot(3/2^{p})=9/2^{p}\ \text{.} (18) Let \boldsymbol{b}_{i} be the i th row of the matrix \mathbf{B} in Equation 6 , as in Equation 11 . Again using the fact that each \boldsymbol{x}_{j}\in\{\boldsymbol{0},\boldsymbol{1}\} , we have |\langle\boldsymbol{b}_{i},(1/2)\cdot\boldsymbol{1}-\boldsymbol{x}^{\prime}\rangle|=\Big|\sum_{j\in\mathrm{vars}(C_{i})}B_{i,j}\cdot(1/2-x_{j}^{\prime})\Big|=\begin{cases}1/2&\text{if $\mathrm{sgndiff}(\boldsymbol{b}_{i},1/2\cdot\boldsymbol{1}-\boldsymbol{x}^{\prime})$ ,}\\ 3/2&\text{otherwise .}\end{cases} (19) Combining Equations 18 and 19 , we have |\langle\boldsymbol{b}_{i},(1/2)\cdot\boldsymbol{1}-\boldsymbol{x}^{\prime}\rangle|^{p}+\sum_{j\in C_{i}}\lVert\mathbf{G}(1/2\cdot\boldsymbol{1}-\boldsymbol{x}_{j})^{\prime}\rVert_{p}^{p}=\begin{cases}10/2^{p}&\text{if $\mathrm{sgndiff}(\boldsymbol{b}_{i},1/2\cdot\boldsymbol{1}-\boldsymbol{x}^{\prime})$ ,}\\ (9+3^{p})/2^{p}&\text{otherwise .}\end{cases} (20) We now lower bound \lVert\mathbf{A}(1/2\cdot\boldsymbol{1}-\boldsymbol{y})\rVert^{p}_{p} . We have that \sum_{j\in\mathrm{vars}(C_{i})}\lVert\mathbf{G}(1/2\cdot\boldsymbol{1}-\boldsymbol{y}_{j})\rVert^{p}_{p}\geq(3/2)^{p}+8/2^{p}\ \text{.} (21) Indeed, by Lemma 3.2 , the terms for which \boldsymbol{y}_{j}\in\{\boldsymbol{0},\boldsymbol{1}\} are equal to 3/2^{p} and the terms in the sum for which \boldsymbol{y}_{j}\notin\{\boldsymbol{0},\boldsymbol{1}\} must have value at least (3/2)^{p}+2/2^{p} . And, since we are only considering constraints C_{i} for which there exists j such that \boldsymbol{y}_{j}\notin\{\boldsymbol{0},\boldsymbol{1}\} , at least one term must have value at least (3/2)^{p}+2/2^{p} . We continue by giving a lower bound for |(1/3)\cdot\boldsymbol{b}_{i}(3/2\cdot\boldsymbol{1}-\boldsymbol{y}^{\text{sum}})| . Here, we observe that (1/2)-(y^{\text{sum}}_{j}/3)\in\{1/6,3/6,5/6\}+\mathbb{Z} . This implies that \displaystyle\langle\boldsymbol{b}_{i},(1/2)\cdot\boldsymbol{1}-\boldsymbol{y}^{\text{sum}}/3\rangle \displaystyle=\Big|\sum_{j\in\mathrm{vars}(C_{i})}B_{i,j}\cdot(1/2-y_{j}^{\text{sum}}/3)\Big| \displaystyle\geq\begin{cases}1/6&\text{if $\mathrm{sgndiff}(\boldsymbol{b}_{i},1/2\cdot\boldsymbol{1}-\boldsymbol{y}^{\text{sum}}/3)$}\\ 1/2&\text{otherwise}\end{cases}\text{,} (22) where the inequality follows by noting that because all three summands in the middle expression are elements of \{1/6,3/6,5/6\}+\mathbb{Z} . If all signs of the summands are the same, one obtains the lower bound 3/6=1/2 , whereas if the signs of the summands differ, one only has the lower bound of 1/6 . By combining Equations 21 and 3.4 , we have the lower bound \displaystyle|\langle\boldsymbol{b}_{i},(1/2)\cdot\boldsymbol{1}-\boldsymbol{y}^{\text{sum}}/3\rangle|^{p}+ \displaystyle\sum_{j\in\mathrm{vars}(C_{i})}\lVert\mathbf{G}(1/2\cdot\boldsymbol{1}-\boldsymbol{y}_{j})\rVert^{p}_{p} \displaystyle\geq\begin{cases}1/6^{p}+(3/2)^{p}+8/2^{p}&\text{if $\mathrm{sgndiff}(\boldsymbol{b}_{i},1/2\cdot\boldsymbol{1}-\boldsymbol{y}^{\text{sum}}/3)$}\\ (9+3^{p})/2^{p}&\text{otherwise}\end{cases}\text{.} (23) Finally, by definition of \boldsymbol{x}^{\prime} ( Equation 17 ), we have that for all j\in[n] , \textrm{sgn}(x_{j}^{\prime}-1/2)=\textrm{sgn}(y_{j}^{\text{sum}}/3-1/2) . Then, it follows that for all i\in[m] that \mathrm{sgndiff}(\boldsymbol{b}_{i},1/2\cdot\boldsymbol{1}-\boldsymbol{x}^{\prime}) if and only if \mathrm{sgndiff}(\boldsymbol{b}_{i},1/2\cdot\boldsymbol{1}-\boldsymbol{y}^{\text{sum}}/3) . By noting that for all p\geq 1 , 2/2^{p}\leq 1/6^{p}+(3/2)^{p} , we combine Equations 20 and 3.4 to obtain that for all i\in[m] , \displaystyle|\langle\boldsymbol{b}_{i},(1/2)\cdot\boldsymbol{1}-\boldsymbol{x}^{\prime}\rangle|^{p}+\sum_{j\in\mathrm{vars}(C_{i})}\lVert\mathbf{G}(1/2\cdot\boldsymbol{1}-\boldsymbol{x}_{j})\rVert_{p}^{p} \displaystyle\leq\ \displaystyle|\langle\boldsymbol{b}_{i},(1/2)\cdot\boldsymbol{1}-\boldsymbol{y}^{\text{sum}}/3\rangle|^{p}+\sum_{j\in\mathrm{vars}(C_{i})}\lVert\mathbf{G}(1/2\cdot\boldsymbol{1}-\boldsymbol{y}_{j})\rVert^{p}_{p}\ \text{,} where we note that the left- and right-hand sides of the inequality are equal to the i th term in the sum in Equation 11 . The result follows. ∎ The following lemma shows soundness for our reduction. Specifically, it shows how to construct an assignment satisfying a large fraction of constraints in an NAE - E 3 - SAT formula \phi from a close vector \mathbf{A}\boldsymbol{x} for \boldsymbol{x}\in\{0,1\}^{3n} to \mathbf{A}(1/2\cdot\boldsymbol{1}_{3n}) , where \mathbf{A}=\mathbf{A}_{p}(\phi) . Lemma 3.6 . Let p\in[1,\infty) , let \phi be an NAE - E 3 - SAT instance with n variables and m constraints, let \mathbf{A}:=\mathbf{A}_{p}(\phi) be as defined in Equation 8 , and let \delta\in[0,1] . Suppose that there exists some vector \boldsymbol{x}:=(\boldsymbol{x}^{1},\boldsymbol{x}^{2},\boldsymbol{x}^{3})\in\mathbb{Z}^{3n} such that \lVert\mathbf{A}((1/2)\cdot\boldsymbol{1}-\boldsymbol{x})\rVert_{p}^{p}\leq\delta m\cdot(10/2^{p})+(1-\delta)m\cdot(9/2^{p}+(3/2)^{p})\ \text{.} (24) Then \mathrm{val}(\phi)\geq\delta . Proof. Suppose that there exists \boldsymbol{x}\in\mathbb{Z}^{3n} satisfying Equation 24 . Then by Lemma 3.5 , we may assume without loss of generality that \boldsymbol{x}=(\boldsymbol{x}^{\prime},\boldsymbol{x}^{\prime},\boldsymbol{x}^{\prime}) for \boldsymbol{x}^{\prime}\in\{0,1\}^{n} and let \boldsymbol{x}_{j}:=(x^{\prime}_{j},x^{\prime}_{j},x^{\prime}_{j}) for each j\in[n] . Therefore, for each i\in[m] , both Equations 18 and 19 hold for \boldsymbol{x} . First, we obtain the bound \displaystyle(1/3^{p})\cdot\lVert\mathbf{B}((3/2)\cdot\boldsymbol{1}-\boldsymbol{x}^{\text{sum}})\rVert^{p}_{p} \displaystyle=\lVert\mathbf{A}((1/2)\cdot\boldsymbol{1}-\boldsymbol{x})\rVert_{p}^{p}-\sum_{j=1}^{n}\deg(v_{j})\cdot\lVert\mathbf{G}((1/2)\cdot\boldsymbol{1}-\boldsymbol{x}_{j})\rVert^{p}_{p} \displaystyle=\lVert\mathbf{A}((1/2)\cdot\boldsymbol{1}-\boldsymbol{x})\rVert_{p}^{p}-m\cdot(9/2^{p}) \displaystyle\leq\delta m\cdot(1/2^{p})+(1-\delta)m\cdot(3/2)^{p}\ \text{,} where the first equality uses Equation 10 with \boldsymbol{y}:=(1/2)\cdot\boldsymbol{1}-\boldsymbol{x} , the second equality uses Equation 18 , and the inequality is by assumption ( Equation 24 ). It then follows from Equation 19 that at least an \delta fraction of indices i\in[m] satisfy \mathrm{sgndiff}(\boldsymbol{b}_{i},1/2\cdot\boldsymbol{1}-\boldsymbol{x}^{\prime}) . Define an assignment \psi to the variables v_{1},\ldots,v_{n} of \phi by \psi(v_{j})=x_{j}^{\prime} . We claim that if \mathrm{sgndiff}(\boldsymbol{b}_{i},1/2\cdot\boldsymbol{1}-\boldsymbol{x}^{\prime}) then \psi satisfies constraint C_{i} , which combined with the fact that at least an \delta fraction of indices i\in[m] satisfy \mathrm{sgndiff}(\boldsymbol{b}_{i},1/2\cdot\boldsymbol{1}-\boldsymbol{x}^{\prime}) , would imply the lemma. It remains to prove the claim. Observe that if constraint C_{i}=\{\ell_{i,1},\ell_{i,2},\ell_{i,3}\} for literals \ell_{i,1},\ell_{i,2},\ell_{i,3} then, as in Equation 14 , (\mathbf{B}(1/2\cdot\boldsymbol{1}-\boldsymbol{x}^{\prime}))_{i}=\sum_{j=1}^{3}\textrm{sgn}(\ell_{i,j})\cdot(1/2-x_{\mathrm{var}(\ell_{i,j})})\ \text{.} Furthermore, as in Equation 15 , for j\in[3] , \textrm{sgn}(\ell_{i,j})\cdot\textrm{sgn}(1/2-x_{\mathrm{var}(\ell_{i,j})})=\begin{cases}-1&\text{if $\psi$ satisfies literal $\ell_{i,j}$ ,}\\ 1&\text{otherwise .}\end{cases} The predicate \mathrm{sgndiff}(\boldsymbol{b}_{i},1/2\cdot\boldsymbol{1}-\boldsymbol{x}^{\prime}) holds exactly when \textrm{sgn}(\ell_{i,j})\cdot(1/2-x_{\mathrm{var}(\ell_{i,j})})=1 for some j\in[3] and \textrm{sgn}(\ell_{i,j})\cdot(1/2-x_{\mathrm{var}(\ell_{i,j})})=-1 for some j\in[3] , meaning that \psi satisfies at least one literal in C_{i} and does not satisfy at least one literal in C_{i} . This in turn implies that \psi satisfies C_{i} , as needed. ∎ 3.5 The Main Theorem We now state and prove the main technical theorem of the paper. Theorem 3.7 . Let \delta,\varepsilon\in\mathbb{R} be such that 0<\delta\leq\varepsilon\leq 1 and let p\in[1,\infty) . There is a polynomial-time mapping reduction from (\delta,\varepsilon) - NAE - E 3 - SAT to \gamma - \mathrm{BinGapCRP}_{p} for \gamma=\gamma(\delta,\varepsilon,p):=\Big(\frac{\delta\cdot 10/2^{p}+(1-\delta)\cdot((3/2)^{p}+9/2^{p})}{\varepsilon\cdot(4/3)^{p}+(1-\varepsilon)2^{p}+3(2+(4/3)^{p})}\Big)^{1/p}\ \text{.} (25) Proof. Let \phi be the input instance of (\delta,\varepsilon) - NAE - E 3 - SAT . Assume that \phi has m constraints. The reduction outputs the \mathrm{BinGapCRP}_{p} instance consisting of the matrix \mathbf{A}=\mathbf{A}_{p}(\phi) defined in Equation 8 and the distance threshold r:=(\varepsilon m\cdot(4/3)^{p}+(1-\varepsilon)m\cdot 2^{p}+3m(2+(4/3)^{p}))^{1/p} defined in Equation 9 . It is clear that the reduction runs in polynomial time, and it remains to show correctness. We start with completeness. If \phi is a YES instance of (\delta,\varepsilon) - NAE - E 3 - SAT , then \lindisc_{p}(\mathbf{A})\leq r by Lemma 3.4 and so the output is a YES instance of \mathrm{BinGapCRP}_{p} . For soundness, we show the contrapositive. Suppose that \mu_{p}(\mathcal{L}(\mathbf{A}))\leq\gamma r=(\delta m\cdot 10/2^{p}+(1-\delta)m\cdot((3/2)^{p}+9/2^{p}))^{1/p}\ \text{.} Then there exists \boldsymbol{y}\in\mathbb{Z}^{3n} such that \lVert\mathbf{A}((1/2\cdot\boldsymbol{1})-\boldsymbol{y})\rVert_{p}\leq\gamma r , and so \mathrm{val}(\phi)\geq\delta by Lemma 3.6 . The result follows. ∎ We conclude by obtaining our main theorem ( Theorem 1.1 ), which asserts that \gamma - \mathrm{BinGapCRP}_{p} is \mathsf{NP} -hard for any constant 1\leq\gamma<\gamma(p) , as a corollary of Theorem 3.7 . Proof of Theorem 1.1 . Let \gamma(p):=\gamma(15/16,1,p) , where \gamma(\cdot,\cdot,\cdot) is as defined in Equation 25 . Then \displaystyle\gamma(p) \displaystyle=\Big(\frac{(15/16)\cdot 10/2^{p}+(1/16)\cdot((3/2)^{p}+9/2^{p})}{(4/3)^{p}+3(2+(4/3)^{p})}\Big)^{1/p} \displaystyle=\Big(\frac{9^{p}+159\cdot 3^{p}}{8^{p+2}+96\cdot 6^{p}}\Big)^{1/p}\ \text{,} By Theorem 2.8 , (15/16+\varepsilon^{\prime},1) -NAE-E3-SAT is \mathsf{NP} -hard for every constant \varepsilon^{\prime}>0 . So, by Theorem 3.7 , \gamma(15/16+\varepsilon^{\prime},1,p) - \mathrm{BinGapCRP} is \mathsf{NP} -hard for every such \varepsilon^{\prime} . The theorem follows by noting that for every constant \varepsilon>0 there exists a constant \varepsilon^{\prime}>0 such that \gamma(15/16+\varepsilon^{\prime},1,p)\geq\gamma(p)-\varepsilon . ∎ 4 \Pi_{2} -hardness of approximating BinaryGapCRP in the \ell_{\infty} norm In this section, we show that the \Pi_{2} -hardness of approximation result for \mathrm{LinDisc}_{\infty} given in Manurangsi [ Man21 ] can be extended to \mathrm{BinGapCRP}_{\infty} . We first give the definition of \forall\exists - NAE - E 3 - SAT , the \Pi_{2} -hard problem that we reduce to approximate \mathrm{BinGapCRP} . \forall\exists - NAE - 3 - SAT (in which constraints may have either two or three literals) was originally shown to be \Pi_{2} -hard in [ EG95 ] , and (a very special case of) \forall\exists - NAE - E 3 - SAT was shown to be \Pi_{2} -hard in [ DDLS20 , Theorem 4.7] . Definition 4.1 ( \forall\exists - NAE - E 3 - SAT ) . The \forall\exists - NAE - E 3 - SAT problem is the decision problem where, on input a NAE - E 3 - SAT formula \phi(V_{A},V_{E}) defined over the disjoint union V_{A}\sqcup V_{E} of variable sets V_{A} and V_{E} , the goal is to distinguish between the following two cases. • (YES instance.) For every assignment \psi_{A}:V_{A}\to\{0,1\} , there exists an assignment \psi_{E}:V_{E}\to\{0,1\} such that (\psi_{A},\psi_{E}) satisfies \phi . • (NO instance.) There exists an assignment \psi_{A}:V_{A}\to\{0,1\} such that for all assignments \psi_{E}:V_{E}\to\{0,1\}) , (\psi_{A},\psi_{E}) does not satisfy \phi . Let \phi(V_{A},V_{E}) be a NAE - E 3 - SAT formula with n^{\prime}=|V_{A}| and n-n^{\prime}=|V_{E}| . We define the matrix \mathbf{A}^{\prime}=\mathbf{A}^{\prime}(\phi) (originally defined in [ Man21 ] ) as \mathbf{A}^{\prime}:=\left(\begin{array}[]{c|c|c|c|c|c|c}\lx@intercol\hfil\mathbf{A}_{\infty}(\phi)\hfil\lx@intercol\vrule\lx@intercol&\mathbf{0}_{n^{\prime}\times n^{\prime}}\\ \hline\cr\frac{2}{3}\mathbf{I}_{n^{\prime}}&\mathbf{0}_{n^{\prime}\times(n-n^{\prime})}&\frac{2}{3}\mathbf{I}_{n^{\prime}}&\mathbf{0}_{n^{\prime}\times(n-n^{\prime})}&\frac{2}{3}\mathbf{I}_{n^{\prime}}&\mathbf{0}_{n^{\prime}\times(n-n^{\prime})}&-2\mathbf{I}_{n^{\prime}}\\ \hline\cr\lx@intercol\hfil\mathbf{0}_{n^{\prime}\times 3n}\hfil\lx@intercol\vrule\lx@intercol&\frac{8}{3}\mathbf{I}_{n^{\prime}}\\ \end{array}\right)\in\mathbb{R}^{(m+3n+2n^{\prime})\times(3n+n^{\prime})}\ \text{,} (26) where \mathbf{A}_{\infty}(\phi) is as defined in Equation 8 and where we have used the notation \mathbf{0}_{m\times n} to denote an m\times n matrix of 0 s. We next give a simple expression for \lVert\mathbf{A}^{\prime}(\boldsymbol{y}^{\prime})\rVert_{\infty} for a vector \boldsymbol{y}^{\prime} in terms of the blocks of \mathbf{A}^{\prime} . Lemma 4.2 ( [ Man21 , Equation 4] ) . Let \phi(V_{A},V_{E}) be an \forall\exists - NAE - E 3 - SAT instance with n^{\prime} universal variables (variables in V_{A} ) and n-n^{\prime} existential variables (variables in V_{E} ), and for each i\in[3] , let \boldsymbol{y}^{i}\in\mathbb{R}^{n} , and let \boldsymbol{y}^{*}\in\mathbb{R}^{n^{\prime}} . Furthermore, let \boldsymbol{y}^{\prime}:=(\boldsymbol{y}^{1},\boldsymbol{y}^{2},\boldsymbol{y}^{3},\boldsymbol{y}^{*})=(\boldsymbol{y},\boldsymbol{y}^{*})\in\mathbb{R}^{3n+n^{\prime}} . Finally, let \boldsymbol{y}^{\text{sum}}=\boldsymbol{y}^{1}+\boldsymbol{y}^{2}+\boldsymbol{y}^{3} . Then \mathbf{A}^{\prime}=\mathbf{A}^{\prime}(\phi) satisfies \lVert\mathbf{A}^{\prime}\boldsymbol{y}^{\prime}\rVert_{\infty}=\max\{\left\lVert\mathbf{A}\boldsymbol{y}\right\rVert_{\infty},\max_{i\in[n^{\prime}]}|(2/3)\cdot y^{\text{sum}}_{i}-2y^{*}_{i}|,(8/3)\cdot\max_{i\in[n^{\prime}]}|y^{*}_{i}|\} (27) Proof. The claim follows by inspection of the blocks of \mathbf{A}^{\prime}\boldsymbol{y}^{\prime} . ∎ We next state the completeness and soundness results from the reduction in [ Man21 ] for showing \Pi_{2} -hardness of \lindisc_{\infty}(A) . Lemma 4.3 (Completeness for \Pi_{2} -hardness reduction, [ Man21 ] ) . Let \phi be an \forall\exists - NAE - E 3 - SAT instance, and \mathbf{A}^{\prime}:=\mathbf{A}^{\prime}(\phi) as defined in Equation 26 . Suppose that \phi is a YES instance. Then \lindisc_{\infty}(\mathbf{A}^{\prime})\leq 4/3 . Proof. The claim follows from the completeness argument in [ Man21 , Proof of Lemma 5] . ∎ Lemma 4.4 (Soundness for \Pi_{2} -hardness reduction, [ Man21 ] ) . Let \phi(V_{A},V_{E}) be an \forall\exists - NAE - E 3 - SAT instance with n^{\prime}:=|V_{A}| universally quantified variables and n:=|V_{A}|+|V_{E}| variables, and let \mathbf{A}^{\prime}=\mathbf{A}^{\prime}(\phi) be as defined in Equation 26 . Suppose that for every \boldsymbol{w}^{\prime}:=(\boldsymbol{w},\boldsymbol{w}^{*}) for \boldsymbol{w}:=1/2\cdot\boldsymbol{1}\in\mathbb{R}^{3n} and \boldsymbol{w}^{*}\in\{1/3,2/3\}^{n} there exists a vector \boldsymbol{x}^{\prime}\in\{0,1\}^{3n+n^{\prime}} such that \lVert\mathbf{A}^{\prime}(\boldsymbol{w}^{\prime}-\boldsymbol{x}^{\prime})\rVert_{\infty}<3/2 . Then \phi is a YES instance of \forall\exists - NAE - E 3 - SAT . Proof. The claim follows from the soundness argument in [ Man21 , Proof of Lemma 5] . ∎ We now state a lemma that guarantees that if a vector \boldsymbol{w}^{\prime} of the form in Lemma 4.4 and \boldsymbol{x}^{\prime}\in\mathbb{Z}^{3n+n^{\prime}} satisfy \lVert\mathbf{A}^{\prime}(\boldsymbol{w}^{\prime}-\boldsymbol{x}^{\prime})\rVert_{\infty}<3/2 , then it must be the case that \boldsymbol{x}^{\prime}\in\{0,1\}^{3n+n^{\prime}} . Lemma 4.5 . Let \phi(V_{A},V_{E}) be an \forall\exists - NAE - E 3 - SAT instance with n^{\prime}:=|V_{A}| universally quantified variables and n:=|V_{A}|+|V_{E}| variables, and let \mathbf{A}^{\prime}=\mathbf{A}^{\prime}(\phi) be as defined in Equation 26 . Furthermore, let \boldsymbol{w}:=1/2\cdot\boldsymbol{1}\in\mathbb{R}^{3n} , let \boldsymbol{w}^{*}\in\{1/3,2/3\}^{n^{\prime}} , let \boldsymbol{x}\in\mathbb{Z}^{3n} , and let \boldsymbol{x}^{*}\in\mathbb{Z}^{n^{\prime}} . Let \boldsymbol{w}^{\prime}:=(\boldsymbol{w},\boldsymbol{w}^{*})\in\mathbb{R}^{3n+n^{\prime}} and let \boldsymbol{x}^{\prime}:=(\boldsymbol{x},\boldsymbol{x}^{*})\in\mathbb{Z}^{3n+n^{\prime}} . Assume that \lVert\mathbf{A}^{\prime}(\boldsymbol{w}^{\prime}-\boldsymbol{x}^{\prime})\rVert_{\infty}<3/2 . Then \boldsymbol{x}^{\prime}\in\{0,1\}^{3n+n^{\prime}} . Proof. We have that \max_{j\in[n]}\lVert\mathbf{G}(\boldsymbol{w}_{j}-\boldsymbol{x}_{j})\rVert_{\infty}\leq\lVert\mathbf{A}(\boldsymbol{w}-\boldsymbol{x})\rVert_{\infty}\leq\lVert\mathbf{A}^{\prime}(\boldsymbol{w}^{\prime}-\boldsymbol{x}^{\prime})\rVert_{\infty}<3/2\ \text{,} (28) where the first inequality follows from the definition of \mathbf{A} ( Equation 8 ), the second inequality follows from Lemma 4.2 , and the third inequality is an assumption. Let \boldsymbol{x}^{1},\boldsymbol{x}^{2},\boldsymbol{x}^{3}\in\mathbb{Z}^{n} be such that \boldsymbol{x}:=(\boldsymbol{x}^{2},\boldsymbol{x}^{2},\boldsymbol{x}^{3}) , and for j\in[n] , let \boldsymbol{x}_{j}:=(x^{1}_{j},x^{2}_{j},x^{3}_{j})\in\mathbb{Z}^{3} . By Equation 28 we then have that for all j\in[n] , \lVert\mathbf{G}(1/2\cdot\boldsymbol{1}-\boldsymbol{x}_{j})\rVert_{\infty}<3/2 . Therefore, by Lemma 3.2 we have have that for all j\in[n] , \boldsymbol{x}_{j}\in\{\boldsymbol{0},\boldsymbol{1}\} . In particular, \boldsymbol{x}\in\{0,1\}^{3n} . Again, by setting \boldsymbol{y}^{\prime}:=\boldsymbol{w}^{\prime}-\boldsymbol{x}^{\prime} in Lemma 4.2 , we have that (8/3)\cdot\max_{i\in[n^{\prime}]}|w^{*}_{i}-x^{*}_{i}|<3/2 , or equivalently, that for all i\in[n^{\prime}] , |w^{*}_{i}-x^{*}_{i}|<9/16<2/3 . It follows that if w_{i}^{*}=1/3 then x_{i}^{*}=0 , and if w_{i}^{*}=2/3 then x_{i}^{*}=1 . In particular, \boldsymbol{x}^{*}\in\{0,1\}^{n^{\prime}} , as needed. ∎ Finally, we obtain the following theorem that adapts [ Man21 , Lemma 5] to the \mathrm{BinGapCRP}_{\infty} problem. Theorem 4.6 . For any constant \varepsilon>0 , there is a polynomial-time mapping reduction from \forall\exists - NAE - E 3 - SAT to (9/8-\varepsilon) - \mathrm{BinGapCRP}_{\infty} . Proof. Let \phi be an instance of the \forall\exists - NAE - E 3 - SAT problem. The reduction outputs the \mathrm{BinGapCRP} instance with matrix \mathbf{A^{\prime}}:=\mathbf{A^{\prime}}(\phi) , as defined in Equation 26 , and distance threshold r:=4/3 . The reduction is efficient by inspection. If \phi is a YES instance, then \lindisc_{\infty}(\mathbf{A}^{\prime})\leq 4/3 by Lemma 4.3 . On the other hand, if \mu_{\infty}(\mathcal{L}(\mathbf{A}^{\prime}))<3/2 , then by definition of the covering radius and Lemma 4.5 we have that for all \boldsymbol{w}^{\prime}:=(\boldsymbol{w},\boldsymbol{w}^{*})\in\mathbb{R}^{3n+n^{\prime}} with \boldsymbol{w}:=1/2\cdot\boldsymbol{1}^{3n} and \boldsymbol{w}^{*}\in\{1/3,2/3\}^{n^{\prime}} , there exists \boldsymbol{x}^{\prime}\in\{0,1\}^{3n+n^{\prime}} such that \lVert\mathbf{A}^{\prime}(\boldsymbol{w}^{\prime}-\boldsymbol{x}^{\prime})\rVert_{\infty}<3/2 . Therefore, \phi is a YES instance by Lemma 4.4 . The result follows. ∎ The proof of Theorem 1.2 now follows easily. Proof of Theorem 1.2 . The result follows from the \Pi_{2} -hardness of \forall\exists - NAE - E 3 - SAT (shown in [ DDLS20 , Theorem 4.7] ) and the reduction in Theorem 4.6 . ∎ Appendix A NP-hardness of (15/16+\varepsilon,1) -NAE-E3-SAT We start with the following theorem of Håstad, which shows that certain 4 -ary CSPs are hard to approximate. 9 9 9 In fact, [ Hs01 , Theorem 7.18] is stated for CSPs over \{-1,1\} rather than \{0,1\} . Theorem A.1 ( [ Hs01 , Theorem 7.18] ) . Let P:\{0,1\}^{4}\to\{0,1\} be a predicate such that P^{-1}(0)\subseteq\{(0,0,0,0),(0,0,1,1),(1,1,0,0),(1,1,1,1)\}\ \text{,} and let \mathrm{CSP}_{P} denote the class of \mathrm{CSP} s where each constraint is P applied to four distinct literals (Boolean variables x_{1},\ldots,x_{n} or their negations). Let \alpha:=\mathbb{E}_{\tau\sim\{0,1\}^{4}}[P(\tau)=1] . Then for every constant \varepsilon\in(0,1-\alpha] , (\alpha+\varepsilon,1) - \mathrm{CSP}_{P} is \mathsf{NP} -hard. The value \alpha:=\mathbb{E}_{\tau\sim\{0,1\}^{4}}[P(\tau)=1] in Theorem A.1 is the expected value of a random assignment to a constraint involving P . Note that if \phi(x_{1},\ldots,x_{n}) is an instance of \mathrm{CSP}_{P} , then by linearity of expectation \alpha is also the expected value of a random assignment to \phi (i.e., \alpha=\mathbb{E}_{\tau\sim\{0,1\}^{n}}[\mathrm{val}_{\tau}(\phi)] ). So, the theorem says that it is \mathsf{NP} -hard to approximate \mathrm{CSP}_{P} even slightly better than what is obtained from a random assignment. We then obtain the following hardness result for NAE - E 4 - SAT from Theorem A.1 . Corollary A.2 . For any constant \varepsilon\in(0,1/8) , (7/8+\varepsilon,1) - NAE - E 4 - SAT is \mathsf{NP} -hard. Proof. Set P:\{0,1\}^{4}\to\{0,1\} to be such that P^{-1}(0):=\{(0,0,0,0),(1,1,1,1)\} , and note that NAE - E 4 - SAT formulas are exactly the class of CSPs where each constraint is P applied to four literals. The result then follows by Theorem A.1 and the observation that \mathbb{E}_{\tau\sim\{0,1\}^{4}}[P(\tau)=1]=7/8 for such P . ∎ We next give a reduction from approximate NAE - E 4 - SAT to approximate NAE - E 3 - SAT . Theorem A.3 . There is a polynomial-time reduction from NAE-E4-SAT instances \phi to NAE-E3-SAT instances \phi^{\prime} such that \mathrm{val}(\phi^{\prime})=\frac{1}{2}(1+\mathrm{val}(\phi)) . Proof. Let P denote the “not all equal” predicate on some number of Boolean inputs. Let \phi(x_{1},\ldots,x_{n}) be the input NAE - E 4 - SAT instance, and assume that \phi has m constraints C_{1},\ldots,C_{m} , each of which is equal to P(\ell_{1},\ell_{2},\ell_{3},\ell_{4}) for four literals \ell_{1},\ell_{2},\ell_{3},\ell_{4} . For i=1,\ldots,m , the reduction introduces the new variable s_{i} , and applies the map C_{i}:=P(\ell_{1},\ell_{2},\ell_{3},\ell_{4})\mapsto\{C_{i}:=P(\ell_{1},\ell_{2},s_{i}),C_{i}^{\prime\prime}:=P(\ell_{3},\ell_{4},\lnot s_{i})\}\ \text{.} It then outputs the NAE - E 3 - SAT formula \phi^{\prime} consisting of the set of 2m constraints \cup_{i=1}^{m}\{C_{i}^{\prime},C_{i}^{\prime\prime}\} . It is clear that the reduction runs in polynomial time, and so it remains to show that \mathrm{val}(\phi^{\prime})=\frac{1}{2}(1+\mathrm{val}(\phi)) . We first show that \mathrm{val}(\phi^{\prime})\geq\frac{1}{2}(1+\mathrm{val}(\phi)) . Let \tau\in\{0,1\}^{n} be an assignment such that \mathrm{val}_{\tau}(\phi)=\mathrm{val}(\phi) . We construct an assignment \tau^{\prime}\in\{0,1\}^{n+s} by assigning the variables x_{1},\ldots,x_{n} as in \tau , and assigning the variables s_{1},\ldots,s_{m} so that: 1. If C_{i} is not satisfied, one of C_{i}^{\prime},C_{i}^{\prime\prime} is satisfied. 2. If C_{i} is satisfied, both of C_{i}^{\prime},C_{i}^{\prime\prime} are satisfied. Item 1 is possible to achieve, e.g., by assigning s_{i}:=\lnot\ell_{i}(\tau) , where we abuse notation slightly and write \ell_{i}(\tau) to denote the evaluation of \ell_{i} on \tau . Item 2 is possible to achieve by considering the following two cases. First, if \ell_{3}(\tau)\neq\ell_{4}(\tau) , then C_{i}^{\prime\prime} is satisfied regardless of s_{i} , and so we assign s_{i}:=\lnot\ell_{1}(\tau) in order to satisfy C_{i}^{\prime} . Second, if \ell_{3}(\tau)=\ell_{4}(\tau) , then we assign s_{i}:=\ell_{3}(\tau) . We claim that both C_{i}^{\prime} and C_{i}^{\prime\prime} are satisfied. Indeed, since \tau satisfied C_{i} and since s_{i}=\ell_{3}(\tau) , we must have that either \ell_{1}(\tau)\neq\ell_{3}(\tau)=s_{i} or \ell_{2}(\tau)\neq\ell_{3}(\tau)=s_{i} . It follows that C_{i}^{\prime} is satisfied. Additionally, C_{i}^{\prime\prime} is satisfied since \lnot s_{i}\neq\ell_{3}(\tau) . We then have that \mathrm{val}(\phi^{\prime})\geq\mathrm{val}_{\tau^{\prime}}(\phi^{\prime})=(2\mathrm{val}(\phi)\cdot m+(1-\mathrm{val}(\phi))\cdot m)/(2m)=\frac{1}{2}(1+\mathrm{val}(\phi)) , as needed. We now show that \mathrm{val}(\phi^{\prime})\leq\frac{1}{2}(1+\mathrm{val}(\phi)) . Let \tau^{\prime}\in\{0,1\}^{n+s} be an assignment such that \mathrm{val}_{\tau^{\prime}}(\phi^{\prime})=\mathrm{val}(\phi^{\prime}) . Let A\in\{0,1,2\} be the random variable defined by sampling uniformly random i\sim[m] and reporting how many of the constraints in the pair C_{i}^{\prime},C_{i}^{\prime\prime} are satisfied by \tau^{\prime} . Note that \mathbb{E}[A]=2\mathrm{val}_{\tau^{\prime}}(\phi^{\prime})=2\mathrm{val}(\phi^{\prime}) . We claim that \mathrm{val}(\phi)\geq\mathrm{val}_{\tau}(\phi)\geq\Pr[A=2] , where \tau\in\{0,1\}^{n} is the restriction of \tau^{\prime} to the variables x_{1},\ldots,x_{n} . Indeed, if \tau^{\prime} satisfies a pair of constraints C_{i}^{\prime}=P(\ell_{1},\ell_{2},s_{i}),C_{i}^{\prime\prime}=P(\ell_{3},\ell_{4},\lnot s_{i}) in \phi^{\prime} for some i\in[m] then \tau satisfies C_{i} in \phi since C_{i}^{\prime},C_{i}^{\prime\prime} are both satisfied only if \ell_{1}(\tau^{\prime}),\ell_{2}(\tau^{\prime}),\ell_{3}(\tau^{\prime}),\ell_{4}(\tau^{\prime}) are not all equal. By applying Markov’s inequality to the nonnegative random variable 2-A , we have that \Pr[A=1]\leq\Pr[A\leq 1]=\Pr[2-A\geq 1]\leq\mathbb{E}[2-A]=2(1-\mathrm{val}(\phi^{\prime}))\ \text{.} (29) Therefore, \displaystyle\mathrm{val}(\phi^{\prime}) \displaystyle=\frac{1}{2}\mathbb{E}[A] \displaystyle=\frac{1}{2}(2\Pr[A=2]+\Pr[A=1]) \displaystyle\leq\Pr[A=2]+1-\mathrm{val}(\phi^{\prime}) \displaystyle\leq\mathrm{val}(\phi)+1-\mathrm{val}(\phi^{\prime})\ \text{,} where the first inequality uses Equation 29 and the second inequality uses the claim that \mathrm{val}(\phi)\geq\Pr[A=2] above. The inequality \mathrm{val}(\phi^{\prime})\leq\frac{1}{2}(1+\mathrm{val}(\phi)) follows by rearranging. ∎ We are now able to conclude our main theorem about the \mathsf{NP} -hardness of (15/16+\varepsilon,1) - NAE - E 3 - SAT as a corollary. Proof of Theorem 2.8 . Combine Corollaries A.2 and A.3 . ∎