Strong Inapproximability for a Promise Rank Problem
Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang · 2026
Read Strong Inapproximability for a Promise Rank Problem by Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11545.txt.
Introduction
Guruswami, Ren and Tang prove strong inapproximability for a promise rank problem. Given a subspace of n by n matrices promised to contain a rank-1 matrix, they show finding a matrix of rank n to a small power is hard. This assumes NP lacks sub-exponential algorithms. Even the exact version's hardness drove recent PCP-free hardness results for minimum distance and shortest vector. The proof combines superposition soundness from Khot and Saket with moment matrices. A second moment-matrix construction runs slower but works for any finite field.
Catalog record
| CREATOR | Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71848 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.11545
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Strong Inapproximability for a Promise Rank Problem Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang Abstract Given a linear subspace of n × n n\times n matrices over 𝔽 2 r \mathbb{F}_{2^{r}} that is promised to contain a matrix of rank 1 1 , we prove that it is hard to find a matrix of rank n o ( 1 / log log n ) n^{o(1/\log\log n)} , assuming NP doesn’t have sub-exponential algorithms. In addition to being a basic problem, the hardness of this problem, even for the exact version, drove recent PCP-free inapproximability results for minimum distance and shortest vector problems concerning codes and lattices. The proof combines the concept of superposition soundness introduced by Khot and Saket with moment matrices. To produce a rank-gap of 1 1 vs. k k , the reduction runs in time n O ( log k ) n^{O(\log k)} . We also give another moment-matrix-based construction which runs in time n O ( k ) n^{O(k)} but works for any finite field 𝔽 q \mathbb{F}_{q} . 1 Introduction Given a linear subspace \mathcal{L}\subseteq\mathbb{F}^{N\times N} that is promised to contain a matrix of rank one, we study the problem of finding a nonzero matrix in \mathcal{L} of minimum rank. This problem is closely related to the problem of finding the minimum rank distance of a rank-metric code [ 5 , 9 , 18 ] . In fact, there is a simple and classical embedding of Hamming-metric codes into this setting. Given a linear code C\subseteq\mathbb{F}^{N} , consider the diagonal matrix code \operatorname{Diag}(C):=\{\operatorname{diag}(c):c\in C\}\subseteq\mathbb{F}^{N\times N}. For every c\in C , \operatorname{rank}(\operatorname{diag}(c))=\|c\|_{0}, and hence the minimum rank distance of \operatorname{Diag}(C) is exactly the minimum Hamming distance of C . Consequently, hardness results for the Minimum Distance Problem (MDP) [ 7 , 4 , 1 , 16 , 3 ] directly translate to hardness for approximating the minimum rank in a matrix subspace. However, this diagonal reduction also explains what it does not prove. The YES case inherited from MDP only promises a nonzero matrix of rank d(C) , the minimum distance of the code, which is generally not 1 . In fact, it is trivial to check if the minimum distance of a code is 1. It is therefore natural to ask whether the problem remains hard under the stronger promise that the subspace contains a nonzero matrix of smallest possible rank, namely rank 1 . A second motivation comes from recent PCP-free inapproximability results for sparse vector problems, including the Minimum Distance Problem and the Shortest Vector Problem [ 3 ] . These reductions start from systems of quadratic equations and view each quadratic constraint as a linear constraint on a matrix: if X=xx^{\top} , then a quadratic form in x becomes a linear form in the entries of X . Hence honest solutions to the original quadratic system correspond to rank-one matrices. The main soundness issue is to rule out spurious higher-rank matrices. In [ 3 ] , this issue is handled via a non-overlap lemma. Specifically, if C is a linear code of distance d(C) over \mathbb{F} , then honest rank-one matrices in the tensor code C\otimes C attain the minimum Hamming weight d(C)^{2} . On the other hand, every matrix in C\otimes C of rank at least 2 has Hamming weight at least \alpha\cdot d(C)^{2} , for some \alpha>1 depending on \mathbb{F} . Thus the Hamming-weight gap driving the MDP hardness is, at its core, a structural gap between rank-one matrices and matrices of rank at least two. This suggests stripping away the Hamming-weight objective and asking for the rank gap directly. In this work, we show strong hardness of distinguishing \exists\,0\neq A\in\mathcal{L}\text{ with }\operatorname{rank}(A)=1\qquad\text{from}\qquad\forall\,0\neq A\in\mathcal{L},\ \operatorname{rank}(A)>k over any fixed finite field of characteristic 2. Specifically, we give a deterministic reduction from 3Sat producing a rank gap of 1 versus k , with matrix dimension n^{O(\log k)} . The resulting inapproximability consequences are summarized in the following main theorem. Theorem 1.1 . Let \operatorname{minrank}(\mathcal{L}):=\min\{\operatorname{rank}(A):0\neq A\in\mathcal{L}\}. For every fixed integer r\geq 1 , no polynomial-time algorithm can, given a linear subspace \mathcal{L}\subseteq\mathbb{F}_{2^{r}}^{N\times N} , distinguish between • (YES) \operatorname{minrank}(\mathcal{L})=1 , • (NO) \operatorname{minrank}(\mathcal{L})>\gamma , in the following regimes: (a) assuming \mathsf{NP}\neq\mathsf{P} , when \gamma>1 is any constant; (b) assuming \mathsf{NP}\nsubseteq\mathsf{DTIME}(2^{\log^{O(1)}n}) , when \gamma=2^{(\log N)^{1-\epsilon}} for any fixed 0<\epsilon<1 ; (c) assuming \mathsf{NP}\nsubseteq\bigcap_{\delta>0}\mathsf{DTIME}(2^{n^{\delta}}) , when \gamma=N^{c/\log\log N} for some fixed constant c>0 . We present the reduction in Section 3 . The proof combines the superposition-soundness framework of Khot and Saket [ 12 ] with linearized moment matrices. A satisfying assignment to the starting quadratic system gives a rank-one moment matrix. Conversely, a low-rank feasible matrix can be decomposed into a bounded number of symmetric rank-one pieces; these pieces behave like several assignments satisfying the quadratic system in superposition. The soundness analysis of Khot–Saket soundness rules out such superpositions, while the moment-matrix equal-union constraints ensure that the remaining zero-sum case cannot hide a nonzero low-rank matrix. We also include a simpler direct moment-matrix reduction in Section 4 . This construction avoids the superposition-soundness and works over every finite field \mathbb{F}_{q} , at the cost of producing matrices of dimension n^{O(k)} . The corresponding inapproximability statement is the following. Theorem 1.2 . Let \operatorname{minrank}(\mathcal{L}):=\min\{\operatorname{rank}(A):0\neq A\in\mathcal{L}\}. For every fixed finite field \mathbb{F}_{q} , no polynomial-time algorithm can, given a linear subspace \mathcal{L}\subseteq\mathbb{F}_{q}^{N\times N} , distinguish between • (YES) \operatorname{minrank}(\mathcal{L})=1 , • (NO) \operatorname{minrank}(\mathcal{L})>\gamma , in the following regimes: (a) assuming \mathsf{NP}\neq\mathsf{P} , when \gamma>1 is any constant; (b) assuming \mathsf{NP}\nsubseteq\mathsf{DTIME}(2^{\log^{O(1)}n}) , when \gamma=(\log N)^{1-\epsilon} for any fixed 0<\epsilon<1 ; (c) assuming \mathsf{NP}\nsubseteq\bigcap_{\delta>0}\mathsf{DTIME}(2^{n^{\delta}}) , when \gamma=c\log N/\log\log N for some fixed constant c>0 . 1.1 Proof overview The key ingredient in both reductions is the pseudo-moment matrix. Fix a moment level d . We introduce a pseudo-moment coordinate y_{R} for every Boolean monomial x^{R}:=\prod_{i\in R}x_{i} of degree at most 2d . Note that the vector (y_{R}) is not assumed to come from an actual Boolean assignment, for which reason it is called pseudo-moment vector. The associated degree- d pseudo-moment matrix 1 1 1 This is the standard moment-matrix object from the Sum-of-Squares literature: for a pseudoexpectation \widetilde{\mathbb{E}} over the Boolean cube, the moment matrix has entries \widetilde{\mathbb{E}}[x^{S}x^{T}]=\widetilde{\mathbb{E}}[x^{S\cup T}] . The Lasserre/SoS hierarchy additionally imposes normalization and positive-semidefiniteness of moment matrix. See, e.g., [ 13 , 17 , 14 , 2 ] . is defined by H_{d}(y)_{S,T}=y_{S\cup T}.\qquad(|S|,|T|\leq d) In the matrix formulation, we impose the equal-union constraints A_{S,T}=A_{S^{\prime},T^{\prime}}\qquad\text{whenever}\qquad S\cup T=S^{\prime}\cup T^{\prime}. This way, the matrix is not an arbitrary linearization of the products x^{S}x^{T} . All factorizations of the same Boolean monomial x^{S\cup T} are forced to share a single pseudo-moment coordinate. This hidden redundancy is what makes rank a useful test. If a pseudo-moment y_{R} is nonzero, it is not isolated in one entry of the matrix: it appears in every entry whose row and column labels union to R . Therefore a feasible low-rank matrix is constrained not only by the original equations, but also by the truncated Boolean monomial algebra encoded by these equal-union identities. We first record the simple but powerful observation related to the rank of pseudo-moment matrices that is used in both reductions, and then give