New Hardness Results for Low-Rank Matrix Completion

This paper presents several new hardness results for low-rank matrix completion problems. We begin by considering the case where the completed matrix is required to be positive semi-definite. Specifically, we study the gap problem $(d_1,d_2,\epsilon )$-PSD-Completion, formally defined below. Here, we let $\mu (B)$ denote the coherence of a matrix $B$, a measure that is always bounded from below by $1$ (see Definition 9).

Note that the definition restricts the magnitudes of the values in the input partial matrix to at most $1$. Such a restriction is essential when allowing an additive error in the completed matrix, as rank is invariant under scaling.

We first point out that, under plausible complexity assumptions related to the Unique Games Conjecture [12, 13], the $(d_1,d_2,\epsilon )$-PSD-Completion problem is intractable for all positive integers $d_2>d_1\ge 3$ and real numbers $\epsilon \in [0,\frac{1}{2})$. Our primary contribution lies in establishing hardness results based solely on the more standard assumption $𝖯\ne \mathrm{𝖭𝖯}$, as stated below.

For admissible values of $d$ and $\epsilon$, Theorem 2 implies that given a partial matrix $A$ with exposed values of magnitude at most $1$, which admits a positive semi-definite completion with coherence $1$ and rank $d$, it is $\mathrm{𝖭𝖯}$-hard to find a positive semi-definite matrix that agrees with each given value of $A$ up to an additive error of at most $\epsilon$, even when the rank is allowed to exceed $d$ by a multiplicative factor of $O(\frac{1}{{\epsilon }^2\cdot \log (1/\epsilon )})$. The theorem encompasses various parameter settings of interest. First, for any fixed approximation factor $\alpha >1$, there exists some constant $\epsilon >0$, for which the $(d,\alpha \cdot d,\epsilon )$-PSD-Completion problem is $\mathrm{𝖭𝖯}$-hard for any sufficiently large integer $d$. Next, letting $\epsilon$ decrease polynomially with $d$ results in a hardness of approximation factor that is polynomial in $d$. Finally, setting $\epsilon =2^{-\mathrm{\Theta }(d)}$ yields a hardness of approximation to within a factor of the form $2^{\mathrm{\Omega }(d)}$. In fact, for an $\epsilon$ that decays sufficiently rapidly with $d$, we obtain the following refined hardness result.

Theorems 2 and 3 substantially strengthen the previously known $\mathrm{𝖭𝖯}$-hardness results for low-rank matrix completion in the positive semi-definite setting. As demonstrated above, our results offer flexibility in the choice of parameters, enabling us to establish hardness for several scenarios of interest. For comparison, the result of [20] is specific to $\epsilon$ decaying polynomially in the rank and achieves $\mathrm{𝖭𝖯}$-hardness of approximation to within factors smaller than $2$. In contrast, for this regime of $\epsilon$, Theorem 2 establishes $\mathrm{𝖭𝖯}$-hardness of approximation to within factors that grow polynomially in the rank. Furthermore, all our hardness results hold even when the completed matrices of $\mathrm{𝖸𝖤𝖲}$ instances are required to have coherence $1$, a property not guaranteed by the $\mathrm{𝖭𝖯}$-hardness result of [20]. Finally, while the hardness result of [10] achieves the same gap as Theorem 3, it is restricted to the non-error setting of $\epsilon =0$.

We turn to our $\mathrm{𝖭𝖯}$-hardness results for the low-rank matrix completion problem, where the completed matrix is constrained by a bounded infinity norm. Consider the gap $(d_1,d_2,\epsilon ,\theta )$-Completion problem, defined as follows.

Our hardness results for this problem are stated as follows.

As mentioned earlier, the previously known hardness results for the $(d_1,d_2,\epsilon ,\theta )$-Completion problem, given in [20], rely on complexity assumptions stronger than the standard conjecture $𝖯\ne \mathrm{𝖭𝖯}$.

Our $\mathrm{𝖭𝖯}$-hardness results are obtained via an efficient reduction from a gap coloring problem, whose hardness was proved by Krokhin, Opršal, Wrochna, and Zivný [28]. Their proof employed the concept of line digraphs, introduced by Harary and Norman [19] in 1960, which lies at the heart of the present paper as well. Specifically, we introduce extensions of the notions of orthogonality dimension and minrank of graphs (see Definitions 15 and 16), and as our main technical contribution, we show that for line digraphs, these quantities are intimately related to the chromatic number. The analysis involves bounds on the rank of perturbed identity matrices that were proved by Alon [2] in 2003 and have found diverse applications (see Theorem 12 and [3]). After establishing hardness results for our extensions of orthogonality dimension and minrank, we derive our hardness results for low-rank matrix completion problems. We believe that these novel graph quantities may be of independent interest, and we encourage their further study by pointing out a close relation to the notion of circular chromatic number, introduced by Vince [37] in 1988 (see Section 3.3).

We provide here an overview of the techniques and ideas behind the proofs of our $\mathrm{𝖭𝖯}$-hardness results for the low-rank matrix completion problem. For concreteness, we focus on the PSD-Completion problem, where the completed matrix is required to be positive semi-definite. We then briefly discuss the setting of a bounded infinity norm.

Our hardness proofs are anchored in the classic gap coloring problem. Recall that the chromatic number of a graph $G$, denoted $\chi (G)$, is the smallest number of colors needed for a vertex coloring of $G$ in which adjacent vertices receive distinct colors. For fixed positive integers , the $(k_1,k_2)$-Coloring problem asks, given an input graph $G$, to distinguish between the case where $\chi (G)\le k_1$ and the case where $\chi (G)\ge k_2$. This problem is known to be intractable for all integers $k_2>k_1\ge 3$, under complexity assumptions related to the Unique Games Conjecture [12, 13]. However, identifying the values of $k_1$ and $k_2$ for which the problem is $\mathrm{𝖭𝖯}$-hard has long been considered notoriously difficult. The current state of the art shows that for every integer $k_1\ge 3$, the problem is $\mathrm{𝖭𝖯}$-hard for $k_2=2k_1$, as proved by Barto, Bulín, Krokhin, and Opršal [5], and for $k_2=\left(\genfrac{}{}{0pt}{}{k_1}{\lfloor k_1/2\rfloor }\right)=2^{(1-o(1))\cdot k_1}$, as proved by Krokhin, Opršal, Wrochna, and Zivný [28]. The latter result, which improves upon the former for all integers $k_1\ge 6$, serves as the starting point of our hardness proofs.

The $\mathrm{𝖭𝖯}$-hardness proof of Krokhin et al. [28] for the gap coloring problem is based on the concept of line digraphs [19], which allows to efficiently shrink the chromatic number of a given graph in a controlled manner. Specifically, for a graph $G$, let $\tilde{\delta }G$ denote the underlying graph of the line digraph of $G$, namely, the graph whose vertices are all the ordered pairs of adjacent vertices in $G$ (whose number is twice the number of edges in $G$), where two vertices $(u_1,u_2)$ and $(v_1,v_2)$ are adjacent in $\tilde{\delta }G$ if $u_2=v_1$ or $u_1=v_2$ (see Definition 20). A result of Poljak and Rödl [34] shows that the chromatic number of the graph $\tilde{\delta }G$ is logarithmic in that of $G$ (see Theorem 21). The hardness result of [28] was derived by repeatedly applying this transformation to instances of the $(k,2^{O(k^{1/3})})$-Coloring problem, the $\mathrm{𝖭𝖯}$-hardness of which was previously proved by Huang [25]. Since the appearance of [28], line digraphs have been effectively utilized in several hardness proofs, e.g., in [17, 10, 24], and they also form a key ingredient in the present paper.

To give a glimpse of the relationship between the chromatic numbers of a graph $G$ and its associated graph $\tilde{\delta }G$, and as a gentle warm-up to our actual argument, let us briefly explain why $\chi (\tilde{\delta }G)\le k$ implies that $\chi (G)\le 2^k$. Indeed, given a proper $k$-coloring of $\tilde{\delta }G$, we define a coloring of $G$ by assigning to each vertex $v$ the set $c(v)$ of colors used at the vertices of the form $(\cdot ,v)$ in $\tilde{\delta }G$ (i.e., vertices whose head is $v$). Clearly, the number of colors used does not exceed $2^k$. To verify that the coloring is proper, observe that if $u$ and $v$ are adjacent vertices in $G$, the color of the vertex $(u,v)$ in $\tilde{\delta }G$ lies in $c(v)$ but not in $c(u)$, ensuring that $c(u)\ne c(v)$. A slightly better upper bound on the chromatic number of $G$, along with a matching lower bound, is provided in [34].

A natural extension of graph colorings, originally proposed by Lovász [31] in the introduction of his renowned $\vartheta$-function, is that of orthonormal representations of graphs. A $d$-dimensional orthonormal representation of a graph is an assignment of a unit vector in ${ℝ}^d$ to each vertex, such that the vectors assigned to adjacent vertices are orthogonal.¹¹1Strictly speaking, the definition in [31] requires vectors assigned to non-adjacent vertices to be orthogonal. This corresponds to an orthonormal representation of the complement graph in our terminology, which we adopt from, e.g., [33, 6] for convenience. The orthogonality dimension of a graph $G$, denoted $\overline{\xi }(G)$, is the smallest integer $d$ for which $G$ admits a $d$-dimensional orthonormal representation (see Definition 15). Note that for every graph $G$, it holds that

Indeed, for the upper bound on $\overline{\xi }(G)$, notice that a proper $k$-coloring of $G$ yields a $k$-dimensional orthonormal representation by assigning the $i$th vector of the standard basis of ${ℝ}^k$ to the vertices of the $i$th color class. For the lower bound, consider a $k$-dimensional orthonormal representation of $G$, and observe that replacing its vectors by their sign vectors in ${\{0,\pm 1\}}^k$ results in a proper coloring of $G$ with $3^k$ colors. For a construction of graphs for which the left-hand side of (1) is tight up to a multiplicative constant, see, e.g., [23]. Now, by associating with each orthonormal representation of $G$ the Gram matrix of its vectors, it follows that $\overline{\xi }(G)$ is the smallest possible rank of a positive semi-definite matrix with ones on the diagonal and zeros in entries that correspond to pairs of adjacent vertices. This formulation naturally connects the problem of determining the orthogonality dimension of a graph to that of determining the minimum rank of a positive semi-definite completion of a suitably defined partial matrix.

The computational hardness of determining the orthogonality dimension of graphs was speculated by Lovász, Saks, and Schrijver [32] in 1989 and has been studied in several recent works, e.g., [6, 16, 10]. We first mention that one may combine the inequalities in (1) with the hardness results of the gap coloring problem from [12, 13] to conclude that deciding whether an input graph $G$ satisfies $\overline{\xi }(G)\le d_1$ or $\overline{\xi }(G)\ge d_2$ is intractable for all integers $d_2>d_1\ge 3$, assuming some variant of the Unique Games Conjecture. This reasoning, however, is insufficient to derive any $\mathrm{𝖭𝖯}$-hardness result for orthogonality dimension, even from the strongest known $\mathrm{𝖭𝖯}$-hardness of gap coloring. Still, it was shown in [10] that for every sufficiently large integer $d$, it is $\mathrm{𝖭𝖯}$-hard to decide whether an input graph $G$ satisfies $\overline{\xi }(G)\le d$ or $\overline{\xi }(G)\ge 2^{(1-o(1))\cdot d/2}$. This result was proved based on the hardness of the $(k,2^{(1-o(1))\cdot k})$-Coloring problem from [28] through the reduction that maps a given graph $G$ to the graph $\tilde{\delta }G$. On the one hand, it follows from (1) that the orthogonality dimension of $\tilde{\delta }G$ does not exceed its chromatic number, which is logarithmic in $\chi (G)$. To complete the correctness of the reduction, it was shown in [10] that $\overline{\xi }(\tilde{\delta }G)\le d$ implies that $\chi (G)\le d^{O(d^2)}$. This, in turn, leads to the $\mathrm{𝖭𝖯}$-hardness of the $d$ vs. $2^{(1-o(1))\cdot d/2}$ gap for the orthogonality dimension problem, as well as for the PSD-Completion problem when no error is allowed.

The argument in [10] was based on the idea outlined below. Suppose that $\overline{\xi }(\tilde{\delta }G)\le d$, and consider a $d$-dimensional orthonormal representation of $\tilde{\delta }G$, which assigns to each ordered pair $e$ of adjacent vertices in $G$ a vector $x_e\in {ℝ}^d$. Associate with each vertex $v$ of $G$ the linear subspace $c(v)\subseteq {ℝ}^d$ spanned by the vectors of the form $x_{(\cdot ,v)}$. Observe that if $u$ and $v$ are adjacent vertices in $G$, their subspaces $c(u)$ and $c(v)$ are quite distant from each other, in the sense that there exists a vector – the vector $x_{(u,v)}$ associated with the vertex $(u,v)$ in $\tilde{\delta }G$ – that lies in $c(v)$ but is orthogonal to the entire subspace $c(u)$. Now, every subspace of ${ℝ}^d$ can be represented by an orthonormal basis of at most $d$ vectors. To obtain a coloring of $G$ with finitely many colors, the basis vectors are replaced by their representatives from a sufficiently dense net of the unit sphere in ${ℝ}^d$, resulting in a proper coloring of $G$ with $d^{O(d^2)}$ colors, as desired.

In order to adapt this approach to the more tolerant setting of PSD-Completion, where an additive error of $\epsilon$ is allowed at each entry of the input partial matrix, we introduce the notion of $d$-dimensional $\epsilon$-orthonormal representations of graphs. Here, each vertex of the graph $G$ at hand is assigned a unit vector in ${ℝ}^d$, such that the inner product of vectors assigned to adjacent vertices is at most $\epsilon$ in absolute value. Letting ${\overline{\xi }}_{\epsilon }(G)$ denote the smallest possible dimension of such an assignment, one can show that approximating the value of ${\overline{\xi }}_{\epsilon }(G)$ for an input graph $G$ is efficiently reducible to approximating the smallest rank of a positive semi-definite matrix that agrees with a given partial matrix, even when an additive error of $O(\epsilon )$ is allowed per entry. To prove the $\mathrm{𝖭𝖯}$-hardness of the former, we apply again the reduction that transforms a graph $G$ into the graph $\tilde{\delta }G$. For correctness, we aim to establish an upper bound on $\chi (G)$ in terms of ${\overline{\xi }}_{\epsilon }(\tilde{\delta }G)$. It turns out, though, that the proof idea of [10], described above, does not extend to this setting. To see why, consider a $d$-dimensional $\epsilon$-orthonormal representation of $\tilde{\delta }G$, which assigns to each ordered pair $e$ of adjacent vertices in $G$ a vector $x_e\in {ℝ}^d$, and as before, associate with each vertex $v$ of $G$ the linear subspace $c(v)\subseteq {ℝ}^d$ spanned by the vectors of the form $x_{(\cdot ,v)}$. Now, let $u$ and $v$ be adjacent vertices in $G$. While the vector $x_{(u,v)}$ still lies in $c(v)$, it is no longer guaranteed to be orthogonal to the subspace $c(u)$. In fact, this vector is only guaranteed to have an inner product of at most $\epsilon$ in absolute value with the vectors of a basis of $c(u)$, which does not even preclude the possibility that it lies in $c(u)$, making it impossible to deduce that $c(u)$ and $c(v)$ are far apart. As an example, consider the two unit vectors $e_1$ and $\sqrt{1-{\epsilon }^2}\cdot e_1+\epsilon \cdot e_2$, where $e_i$ denotes the $i$th vector of the standard basis of ${ℝ}^d$. Notice that the vector $e_2$ has an inner product of at most $\epsilon$ in absolute value with each of the two vectors, yet it lies within the subspace they span.

We overcome the above difficulty through a different coloring of $G$. Namely, for each vertex $v$ of $G$, we consider a maximal set $c(v)\subseteq {ℝ}^d$ of vectors of the form $x_{(\cdot ,v)}$ with pairwise inner products of absolute value at most ${\epsilon }^{\prime }$, for some appropriately chosen ${\epsilon }^{\prime }>\epsilon$. Now, if $u$ and $v$ are adjacent vertices in $G$, then the vector $x_{(u,v)}$ has an inner product of at most $\epsilon$ in absolute value with each vector of $c(u)$. However, by the maximality of $c(v)$, there must exist a vector in $c(v)$ whose inner product with $x_{(u,v)}$ is larger than ${\epsilon }^{\prime }$ in absolute value: either $x_{(u,v)}$ itself or some other vector that prevented it from being added to $c(v)$. This, in a sense, implies that the sets $c(u)$ and $c(v)$ are sufficiently far apart, so that they remain distinct once their vectors are replaced by representatives from a sufficiently dense net. Yet, the number of vectors in the sets $c(v)$ has a significant effect on the number of colors used. In contrast to the $\epsilon =0$ setting, here we do not handle bases of subspaces of ${ℝ}^d$, and therefore, we cannot ensure that the size of each set $c(v)$ is bounded by $d$. We do know that the vectors of each set $c(v)$ are nearly orthogonal to each other, with the absolute value of their pairwise inner products at most ${\epsilon }^{\prime }$. To bound their size, we apply bounds of Alon [2] on the rank of perturbed identity matrices (see Theorem 12). When ${\epsilon }^{\prime }$ is sufficiently small, namely, ${\epsilon }^{\prime }\le O(1/\sqrt{d})$, it turns out that each set $c(v)$ includes fewer than $2d$ vectors. For larger values of ${\epsilon }^{\prime }$, the bound weakens, leading to the dependence of the hardness gap on the error $\epsilon$, as stated in Theorem 2.

To extend our approach to the low-rank matrix completion problem with a bounded infinity norm, we introduce an extension of the notion of graph-fitting matrices, proposed by Haemers in [18]. Here, for a graph $G$, we consider matrices (not necessarily positive semi-definite) that have ones on the diagonal and values of magnitude at most $\epsilon$ in entries corresponding to adjacent vertices (see Definition 16). Our main technical result provides an upper bound on the chromatic number of a graph $G$, assuming that the graph $\tilde{\delta }G$ admits such a matrix with a bounded rank and a bounded infinity norm (see Theorem 22). The proof generalizes the technique described above, drawing on the fact that every matrix has a rank factorization involving matrices with rows of bounded norm (see Lemma 8). The detailed argument is presented in the subsequent technical sections.

The rest of the paper is organized as follows. In Section 2, we collect several notations and tools that will be used throughout the paper. In Section 3, we define and study nearly orthonormal representations of graphs, with particular attention to line digraphs. In Section 4, we apply our insights to establish the hardness of a problem we call Graph Fitness. This, in turn, leads to the hardness of the $(d_1,d_2,\epsilon )$-PSD-Completion and $(d_1,d_2,\epsilon ,\theta )$-Completion problems, thereby verifying Theorems 2, 3, 5, and 6. Due to space limitations, some proofs and results are deferred to the full version of the paper.

For a positive integer $d$, let $⟨\cdot ,\cdot ⟩$ and $\parallel \cdot \parallel$ stand for the standard inner product and Euclidean norm on ${ℝ}^d$, respectively. As is customary, a vector $x\in {ℝ}^d$ with $\Vert x\Vert =1$ is referred to as a unit vector. The following simple claim will be used.

For a real matrix $A=(a_{i,j})$, let $rank(A)$ denote its rank over $ℝ$, and let ${\Vert A\Vert }_{\mathrm{\infty }}$ denote its infinity norm, defined by ${\Vert A\Vert }_{\mathrm{\infty }}={\max }_{i,j}|a_{i,j}|$. It is well known that every matrix $A\in {ℝ}^{n\times n}$ of rank $d$ can be expressed as $A=X\cdot Y^t$ for some matrices $X,Y\in {ℝ}^{n\times d}$. The following lemma guarantees the existence of such a factorization with matrices $X$ and $Y$ whose rows have bounded norms. Its proof relies on John’s classical theorem from Banach space theory and can be found, e.g., in [35, Corollary 2.2].

A matrix $A\in {ℝ}^{n\times n}$ is said to be positive semi-definite if $x^{t}Ax\ge 0$ for all vectors $x\in {ℝ}^n$. This condition is equivalent to the existence of a matrix $X\in {ℝ}^{n\times d}$ such that $A=X\cdot X^t$ where $d=rank(A)$. The coherence of a symmetric matrix measures the extent to which its row (or column) space aligns with the vectors of the standard basis. It is formally defined as follows.

For a positive integer $d$ and a real number $\theta >0$, let $B_d(\theta )$ denote the closed $d$-dimensional ball of radius $\theta$ centered at the origin, i.e., $B_d(\theta )=\{x\in {ℝ}^d\mid \Vert x\Vert \le \theta \}$. We define a net for a closed ball as follows.

Note that Definition 10 requires every point in the ball to admit a point in the $\eta$-net at a distance strictly smaller than $\eta$. We need the following standard lemma on the existence of bounded-size nets for balls (see, e.g., [15]).

It is well known and easy to verify that if a matrix $A=(a_{i,j})\in {ℝ}^{m\times m}$ satisfies $a_{i,i}=1$ for all $i\in [m]$ and $|a_{i,j}|\le \frac{1}{m}$ for all distinct $i,j\in [m]$, then $A$ has full rank. The following theorem, proved by Alon [2], provides lower bounds on the rank of a symmetric matrix under a weaker assumption on its off-diagonal entries. For a variety of applications of these bounds, the reader is referred to [3] (see also [4]).

In light of Theorem 12, we introduce the quantities $m(d,\epsilon )$, defined as follows.

Note that for all positive integers $d$ and real numbers $\epsilon \le {\epsilon }^{\prime }$, it holds that $m(d,\epsilon )\le m(d,{\epsilon }^{\prime })$.

As a direct corollary of Theorem 12, we obtain the following bounds on $m(d,\epsilon )$. A proof is provided in the full version of the paper.

For a positive integer $k$, a $k$-coloring of a graph $G$ is a mapping from the vertex set of $G$ to a set of size $k$. A coloring $c$ of $G$ is called proper if $c(u)\ne c(v)$ whenever $u$ and $v$ are adjacent vertices in $G$. The graph $G$ is called $k$-colorable if it admits a proper $k$-coloring, and the smallest integer $k$ for which $G$ is $k$-colorable is called the chromatic number of $G$ and is denoted by $\chi (G)$. Observe that any proper $k$-coloring of $G$ induces a $k$-dimensional orthonormal representation of $G$, in which the vertices of the $i$th color class are assigned the $i$th vector of the standard basis of ${ℝ}^k$. Consequently, every graph $G$ satisfies $\overline{\xi }(G)\le \chi (G)$ and thus admits a positive semi-definite matrix of rank at most $\chi (G)$ that fits it (see Remark 17). The following simple lemma, whose argument is borrowed from [20], shows that a slight modification of $G$ ensures the existence of such a matrix with minimal coherence (recall Definition 9). The proof is deferred to the full version of the paper.

The following theorem relates the chromatic number of a graph to the rank of a matrix that nearly fits it. A similar reasoning appears in [20]. The proof is given in the full version of the paper.

The concept of line digraphs, introduced in [19], is defined as follows.

The following result, proved by Poljak and Rödl [34] (see also [21]), shows that the chromatic number of a graph $G$ determines the chromatic number of $\tilde{\delta }G$. The statement involves the function $b:\mathbb{N}\to \mathbb{N}$, defined by $b(n)=\left(\genfrac{}{}{0pt}{}{n}{\lfloor n/2\rfloor }\right)$.

The following theorem ties the chromatic number of a graph to the rank of a symmetric matrix that nearly fits the underlying graph of its line digraph. It plays a crucial role in our $\mathrm{𝖭𝖯}$-hardness results. The statement involves the quantities $m(d,\epsilon )$ given in Definition 13.

The circular chromatic number of graphs, introduced by Vince [37], has several equivalent definitions, one of which is presented below. For a comprehensive introduction to the topic, the reader is referred to the survey [38].

It is known that the infimum in the definition of ${\chi }_c(G)$ is always attained (at a rational number), hence the infimum can be replaced by a minimum. It is also known that any graph $G$ satisfies $\chi (G)=\lceil {\chi }_c(G)\rceil$. The following observation relates the circular chromatic number to $2$-dimensional nearly orthonormal representations. Note that every graph $G$ with at least one edge satisfies ${\chi }_c(G)\ge 2$.

The Graph Fitness problem is defined as follows.

Note that the condition on $\mathrm{𝖸𝖤𝖲}$ instances in the above definition implies the existence of a matrix $X\in {ℝ}^{n\times d_1}$ whose rows have norm $1$, such that $X\cdot X^t$ is a symmetric matrix that fits the graph $G$. Therefore, the $\mathrm{𝖸𝖤𝖲}$ and $\mathrm{𝖭𝖮}$ instances of the problem do not overlap.

We state two efficient reductions from the $(k_1,k_2)$-Coloring problem to the $(d_1,d_2,\epsilon ,\theta )$-Graph-Fitness problem for suitable choices of parameters. The proofs can be found in the full version of the paper. The first reduction builds on Theorem 19.

The next reduction between the problems relies on Theorem 22 and is crucial for deriving our $\mathrm{𝖭𝖯}$-hardness results from Theorem 26. Note that the reduction from Lemma 28 is insufficient for this purpose. The statement involves the quantities $m(d,\epsilon )$ from Definition 13 and the function $b:\mathbb{N}\to \mathbb{N}$ from Theorem 26.

We next state an $\mathrm{𝖭𝖯}$-hardness result for the Graph Fitness problem. The (somewhat tedious) proof, which is omitted here, integrates the hardness of the gap coloring problem from Theorem 26, the reduction to Graph Fitness provided by Lemma 30, and the bounds on the quantities $m(d,\epsilon )$ from Corollary 14.

Theorem 31 establishes the $\mathrm{𝖭𝖯}$-hardness of the Graph Fitness problem for general parameter settings. To illustrate its applicability, we present three implications below. The first provides an exponential gap in the rank for an exponentially small error, the second offers a polynomial gap in the rank along with a polynomial decay of the error, and the third shows a constant multiplicative gap in the rank for a constant error.

We finally turn to proving our hardness results for the low-rank matrix completion problems described in Definitions 1 and 4, thereby strengthening the $\mathrm{𝖭𝖯}$-hardness results of [20]. This will be accomplished through the reductions outlined in the following lemma.