Strong Inapproximability for a Promise Rank Problem
Provides strong inapproximability for a basic promise rank problem, with implications for hardness of coding and lattice problems.
The paper proves that, given a linear subspace of matrices over a finite field promised to contain a rank-1 matrix, it is hard to find a matrix of rank n^{o(1/\\log\\log n)} unless NP has sub-exponential algorithms. This result drives PCP-free inapproximability for minimum distance and shortest vector problems.
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$.