2026-09-17T02:04:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24144 2026-09-05T18:34:15Z ddc:004 open_access

New Hardness Results for Low-Rank Matrix Completion Chawin, Dror Haviv, Ishay hardness of approximation low-rank matrix completion graph coloring 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dror Chawin and Ishay Haviv 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.37 urn:nbn:de:0030-drops-241448 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.37 eng https://creativecommons.org/licenses/by/4.0/legalcode