DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.19

Strong Inapproximability for a Promise Rank Problem

Authors: Venkatesan Guruswami, Xuandi Ren, and Shaoxuan Tang

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

Given a linear subspace of n × n matrices over 𝔽_{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 F_q.

Cite as

Venkatesan Guruswami, Xuandi Ren, and Shaoxuan Tang. Strong Inapproximability for a Promise Rank Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2026.19,
  author =	{Guruswami, Venkatesan and Ren, Xuandi and Tang, Shaoxuan},
  title =	{{Strong Inapproximability for a Promise Rank Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{19:1--19:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.19},
  URN =		{urn:nbn:de:0030-drops-277360},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.19},
  annote =	{Keywords: rank minimization, inapproximability, promise problems, PCP, moment matrices}
}

Search Results

Documents authored by Tang, Shaoxuan

Strong Inapproximability for a Promise Rank Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message