The low-rank matrix completion problem asks whether a given real matrix with missing values can be completed so that the resulting matrix has low rank or is close to a low-rank matrix. The completed matrix is often required to satisfy additional structural constraints, such as positive semi-definiteness or a bounded infinity norm. The problem arises in various research fields, including machine learning, statistics, and theoretical computer science, and has broad real-world applications. This paper presents new NP-hardness results for low-rank matrix completion problems. We show that for every sufficiently large integer d and any real number ε ∈ [2^{-O(d)},1/7], given a partial matrix A with exposed values of magnitude at most 1 that admits a positive semi-definite completion of rank d, it is NP-hard to find a positive semi-definite matrix that agrees with each given value of A up to an additive error of at most ε, even when the rank is allowed to exceed d by a multiplicative factor of O (1/(ε²⋅log(1/ε))). This strengthens a result of Hardt, Meka, Raghavendra, and Weitz (COLT, 2014), which applies to multiplicative factors smaller than 2 and to ε that decays polynomially in d. We establish similar NP-hardness results for the case where the completed matrix is constrained to have a bounded infinity norm (rather than be positive semi-definite), for which all previous hardness results rely on complexity assumptions related to the Unique Games Conjecture. Our proofs involve a novel notion of nearly orthonormal representations of graphs, the concept of line digraphs, and bounds on the rank of perturbed identity matrices.

For a field $\mathbb{F}$ and integers $d$ and $k$, a set of vectors of $\mathbb{F}^d$ is called $k$-nearly orthogonal if its members are non-self-orthogonal and every $k+1$ of them include an orthogonal pair. We prove that for every prime $p$ there exists a positive constant $δ= δ(p)$, such that for every field $\mathbb{F}$ of characteristic $p$ and for all integers $k \geq 2$ and $d \geq k^{1/(p-1)}$, there exists a $k$-nearly orthogonal set of at least $d^{δ\cdot k^{1/(p-1)}/ \log k}$ vectors of $\mathbb{F}^d$. In particular, for the binary field we obtain a set of $d^{Ω( k /\log k)}$ vectors, and this is tight up to the $\log k$ term in the exponent. For comparison, the best known lower bound over the reals is $d^{Ω( \log k / \log \log k)}$ (Alon and Szegedy, Graphs and Combin., 1999). The proof combines probabilistic and spectral arguments.

The index coding problem is concerned with the amount of information that a sender has to transmit to multiple receivers in a way that enables each of them to retrieve its requested data relying on prior side information. For linear index coding, the problem is characterized by the minrank parameter of a graph that represents the side information map of the receivers. Previous work has shown that it is$\mathsf {NP}$-hard to determine the minrank parameter of graphs. In this work, we study the computational complexity of the minrank parameter on perturbed instances, obtained from worst-case instances by a random extension of the side information available to the receivers. This setting is motivated by applications of index coding, in which the side information is accumulated via repeated transmissions that suffer from loss of data due to noisy communication or storage capacity. We prove that determining the minrank parameter remains computationally hard on perturbed instances. Our contribution includes an extension of several hardness results of the minrank parameter to the perturbed setting as well as a general technique for deriving the hardness of the minrank parameter on perturbed instances from its hardness on worst-case instances.

The index coding problem is concerned with broadcasting encoded information to a collection of receivers in a way that enables each receiver to discover its required data based on its side information, which comprises the data required by some of the others. Given the side information map, represented by a graph in the symmetric case and by a digraph otherwise, the goal is to devise a coding scheme of minimum broadcast length. We present a general method for developing efficient algorithms for approximating the index coding rate for prescribed families of instances. As applications, we obtain polynomial-time algorithms that approximate the index coding rate of graphs and digraphs on n vertices to within factors of$O(n/\log ^{2} n)$and$O(n/\log n)$respectively. This improves on the approximation factors of$O(n/\log n)$for graphs and$O(n \cdot \log \log n/\log n)$for digraphs achieved by Blasiak, Kleinberg, and Lubetzky. For the family of quasi-line graphs, we exhibit a polynomial-time algorithm that approximates the index coding rate to within a factor of 2. This improves on the approximation factor of$O(n^{2/3})$achieved by Arbabjolfaei and Kim for graphs on n vertices taken from certain sub-families of quasi-line graphs. Our approach is applicable for approximating a variety of additional graph and digraph quantities to within the same approximation factors. Specifically, it captures every graph quantity sandwiched between the independence number and the clique cover number and every digraph quantity sandwiched between the maximum size of an acyclic induced sub-digraph and the directed clique cover number.

The orthogonality dimension of a graph G over ℝ is the smallest integer k for which one can assign a nonzero k-dimensional real vector to each vertex of G, such that every two adjacent vertices receive orthogonal vectors. We prove that for every sufficiently large integer k, it is NP-hard to decide whether the orthogonality dimension of a given graph over ℝ is at most k or at least 2^{(1-o(1))⋅k/2}. We further prove such hardness results for the orthogonality dimension over finite fields as well as for the closely related minrank parameter, which is motivated by the index coding problem in information theory. This in particular implies that it is NP-hard to approximate these graph quantities to within any constant factor. Previously, the hardness of approximation was known to hold either assuming certain variants of the Unique Games Conjecture or for approximation factors smaller than 3/2. The proofs involve the concept of line digraphs and bounds on their orthogonality dimension and on the minrank of their complement.

Abstract. The orthogonality dimension of a graph [Formula: see text] over [Formula: see text] is the smallest integer [Formula: see text] for which one can assign a nonzero [Formula: see text]-dimensional real vector to each vertex of [Formula: see text] such that every two adjacent vertices receive orthogonal vectors. We prove that for every sufficiently large integer [Formula: see text], it is [Formula: see text]-hard to decide whether the orthogonality dimension of a given graph over [Formula: see text] is at most [Formula: see text] or at least [Formula: see text]. We further prove such hardness results for the orthogonality dimension over finite fields as well as for the closely related minrank parameter, which is motivated by the index coding problem in information theory. This in particular implies that it is [Formula: see text]-hard to approximate these graph quantities to within any constant factor. Previously, the hardness of approximation was known to hold either assuming certain variants of the unique games conjecture or for approximation factors smaller than [Formula: see text]. The proofs involve the concept of line digraphs and bounds on their orthogonality dimension and on the minrank of their complement.