Strong Inapproximability for a Promise Rank Problem
Pith reviewed 2026-05-13 02:07 UTC · model grok-4.3
The pith
Given a linear subspace of n by n matrices promised to contain a rank-1 matrix over a finite field, no efficient algorithm can find a matrix of rank smaller than n to the power of a tiny fraction of 1 over log log n.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Given a linear subspace of n × n matrices over F_{2^r} that is promised to contain a matrix of rank 1, it is hard to find a matrix of rank n^{o(1/log log n)}, assuming NP does not have sub-exponential algorithms. The proof combines superposition soundness with moment matrices to produce the rank gap; one construction achieves this in time n^{O(log k)} while a second works over any finite field F_q in time n^{O(k)}.
What carries the argument
Moment matrices paired with superposition soundness to enforce the rank-1 promise and create a controlled gap between rank 1 and rank k in the output subspace.
If this is right
- The exact minimum-rank problem in these subspaces inherits the same strong inapproximability.
- Hardness of this promise problem can be used directly to obtain PCP-free inapproximability for minimum distance of linear codes and shortest vector problems in lattices.
- For any k the reduction that creates a 1-versus-k rank gap runs in time n to the power O(log k).
- A separate moment-matrix construction yields the same hardness over an arbitrary finite field in time n to the power O(k).
Where Pith is reading between the lines
- The same technique may transfer to other promise problems that ask for low-degree or low-rank solutions in algebraic varieties.
- If the exponent in the approximation factor can be improved, it would likely require a different soundness property or a faster matrix construction.
- The result suggests that promise-based starting points can sometimes replace PCPs without sacrificing the strength of the final inapproximability.
Load-bearing premise
NP cannot be solved in sub-exponential time.
What would settle it
A polynomial-time algorithm that outputs a matrix of rank n^{o(1/log log n)} from any such promised subspace.
Figures
read the original abstract
Given a linear subspace of $n \times n$ matrices over $\mathbb F_{2^r}$ that is promised to contain a matrix of rank $1$, we prove that it is hard to find a matrix of rank $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$ vs. $k$, the reduction runs in time $n^{O(\log k)}$. We also give another moment-matrix-based construction which runs in time $n^{O(k)}$ but works for any finite field $\mathbb F_q$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that, assuming NP has no sub-exponential algorithms, it is hard to find a matrix of rank n^{o(1/log log n)} inside an n×n linear subspace over F_{2^r} that is promised to contain a rank-1 matrix. The argument combines superposition soundness with moment matrices to obtain a rank gap of 1 versus k; the reduction runs in time n^{O(log k)}. A second moment-matrix construction is given that works over arbitrary finite fields F_q but requires time n^{O(k)}.
Significance. If the central reduction and hardness transfer are correct, the result supplies a strong basic promise problem whose exact version already underlies recent PCP-free inapproximability theorems for minimum-distance and shortest-vector problems. The explicit reduction-time bounds and the superposition-soundness technique constitute a technical contribution that clarifies the parameter regime.
major comments (1)
- [Abstract] Abstract and reduction description: the stated running time n^{O(log k)} with k = n^{o(1/log log n)} produces an instance whose size is polynomial in the original NP instance size m, yet the composed running time remains sub-exponential in m. This means the assumption only rules out 2^{o(n^δ)} algorithms for the promise-rank problem rather than all sub-exponential algorithms, weakening the claimed transfer. The precise m-to-n relation and the exact sub-exponential bound being contradicted must be stated explicitly in the reduction analysis.
minor comments (1)
- The abstract refers to the exact version driving prior results but supplies no citation or one-sentence recap of those results; adding a short pointer would improve context without lengthening the abstract.
Simulated Author's Rebuttal
We thank the referee for the careful reading and for highlighting the need for greater precision in the reduction parameters and hardness transfer. We address the comment below and will incorporate the requested clarifications.
read point-by-point responses
-
Referee: [Abstract] Abstract and reduction description: the stated running time n^{O(log k)} with k = n^{o(1/log log n)} produces an instance whose size is polynomial in the original NP instance size m, yet the composed running time remains sub-exponential in m. This means the assumption only rules out 2^{o(n^δ)} algorithms for the promise-rank problem rather than all sub-exponential algorithms, weakening the claimed transfer. The precise m-to-n relation and the exact sub-exponential bound being contradicted must be stated explicitly in the reduction analysis.
Authors: We agree that an explicit parameter analysis strengthens the presentation. In the revised version we will add a dedicated paragraph in Section 3 (Reduction) stating that the construction sets n = m^{O(1)} and that the reduction runs in time 2^{o(m^δ)} for every δ > 0. Consequently, any algorithm for the promise-rank problem running in time 2^{n^δ} (any fixed δ > 0) would compose to a 2^{m^δ}-time algorithm for the original NP instance. Since 2^{m^δ} is subexponential, the assumption that NP has no subexponential algorithms (i.e., NP ⊈ SUBEXP) directly implies that the promise-rank problem admits no 2^{n^δ}-time algorithm for any δ > 0 and therefore has no subexponential algorithm at all. This transfer is not weakened; the o(1/log log n) in the rank gap is chosen precisely so that the reduction exponent remains o(n^δ) for every δ. We will also update the abstract to reference this clarified bound. revision: yes
Circularity Check
No circularity: reduction establishes hardness independently of inputs
full rationale
The paper proves inapproximability via an explicit reduction that combines superposition soundness (from Khot-Saket) with moment matrices to create a rank gap. The reduction time bound n^{O(log k)} and the resulting hardness statement under the subexponential-NP assumption are derived from the construction itself rather than by redefining or fitting the target quantity. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation chain. The central claim remains a non-tautological consequence of the reduction.
Axiom & Free-Parameter Ledger
Reference graph
Works this paper leans on
-
[1]
Israel Journal of Mathematics , volume =
Dinur, Irit and Guruswami, Venkatesan , title =. Israel Journal of Mathematics , volume =. 2015 , doi =
work page 2015
-
[2]
arXiv preprint arXiv:1504.03923 , year =
Sangxia Huang , title =. arXiv preprint arXiv:1504.03923 , year =
-
[3]
Jean B. Lasserre , title =. SIAM Journal on Optimization , volume =. 2001 , doi =
work page 2001
-
[4]
Pablo A. Parrilo , title =. Mathematical Programming , volume =. 2003 , doi =
work page 2003
-
[5]
Emerging Applications of Algebraic Geometry , editor =
Monique Laurent , title =. Emerging Applications of Algebraic Geometry , editor =. 2009 , doi =
work page 2009
-
[6]
Proceedings of the International Congress of Mathematicians (ICM) , year =
Boaz Barak and David Steurer , title =. Proceedings of the International Congress of Mathematicians (ICM) , year =
-
[7]
Vijay Bhattiprolu and Venkatesan Guruswami and Euiwoong Lee and Xuandi Ren , title =. 66th. 2025 , url =. doi:10.1109/FOCS63196.2025.00068 , timestamp =
-
[8]
2014 IEEE 29th Conference on Computational Complexity (CCC) , pages=
Locally dense codes , author=. 2014 IEEE 29th Conference on Computational Complexity (CCC) , pages=. 2014 , organization=
work page 2014
-
[9]
IEEE Transactions on Information Theory , volume=
A simple deterministic reduction for the gap minimum distance of code problem , author=. IEEE Transactions on Information Theory , volume=. 2014 , publisher=
work page 2014
-
[10]
A Deterministic Reduction for the Gap Minimum Distance Problem , year=
Cheng, Qi and Wan, Daqing , journal=. A Deterministic Reduction for the Gap Minimum Distance Problem , year=
-
[11]
IEEE Transactions on Information Theory , volume=
Hardness of approximating the minimum distance of a linear code , author=. IEEE Transactions on Information Theory , volume=. 2003 , publisher=
work page 2003
- [12]
-
[13]
On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes , journal =
Philippe Gaborit and Gilles Z. On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes , journal =. 2016 , doi =
work page 2016
-
[14]
Designs, Codes and Cryptography , volume =
Alberto Ravagnani , title =. Designs, Codes and Cryptography , volume =. 2016 , doi =
work page 2016
-
[15]
Fraenkel, Aviezri S. and Yesha, Yaacov , title =. Discrete Applied Mathematics , volume =
- [16]
- [17]
-
[18]
Super-polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes , journal =
Venkatesan Guruswami and Prahladh Harsha and Johan H. Super-polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes , journal =. 2017 , doi =
work page 2017
- [19]
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.