Nelson–Nguyen conjecture on sparse oblivious subspace embeddings

Less than 1 year old · traced to 2026

Fix a subspace dimension $d$ and distortion parameters $\alpha = \beta \in (0,1)$ . A random sparse matrix $\bm{\Phi}: \mathbb{R}^n \to \mathbb{R}^k$ has at most $\zeta$ nonzero entries per column and embedding dimension $k$ . Nelson–Nguyen conjecture. There exists a construction satisfying

\zeta \leq \operatorname{Const} \cdot \alpha^{-1} \log d \quad\text{and}\quad k \leq \operatorname{Const} \cdot \alpha^{-2} \log d.

For any fixed subspace of dimension $d$ , with probability at least $1-d^{-1}$ , this matrix is a subspace embedding with distortion parameters $\alpha,\beta$ , where the constants are universal. The conjecture concerns achieving near-logarithmic column sparsity and embedding dimension for oblivious subspace embeddings; its resolution is not established in the supplied source.

References

Primary source

Joel A. Tropp, “Comparison theorems for the extreme eigenvalues of a random symmetric matrix”, arXiv:2603.04365 (2026).

Posted 1 month ago · edited 2 weeks ago

Progress summary

Refreshed 2 weeks ago

Claimed solved

A September 2026 paper claims a complete proof of the conjecture, but independent mathematical verification is still absent.

Nelson and Nguyen posed the conjecture at FOCS 2013: sparse oblivious embeddings should simultaneously attain near-logarithmic column sparsity and near-optimal embedding dimension for every fixed subspace.

Known results

Nelson and Nguyen (2013): sparsity $O(\log^3 d/\varepsilon)$ and dimension $O(d\log^8 d/\varepsilon^2)$ .
Cohen (2016): sparsity $O(\log d/\varepsilon)$ and dimension $O(d\log d/\varepsilon^2)$ .
Chenakkod, Dereziński, Dong, and Rudelson (2025): optimal dimension with sub-polylogarithmic sparsity losses.
A 2025 result gives $\widetilde O(d/\varepsilon^2)$ rows and $\widetilde O(\log d/\varepsilon)$ nonzeros per column.

September 2026 claimed proof; Community submission (unverified)

On September 2, 2026, Diar Heidary’s paper SparseStack Is an Optimal Oblivious Subspace Embedding claimed the exact bounds $m=O((d+\log(1/\delta))/\varepsilon^2)$ and $s=O(\log(d/\delta)/\varepsilon)$ , with a Lean 4 formalization; this claim has not been independently verified. A submission posted August 14, 2026, argues for the same bounds and says that $5.6$ Sol and Fable 5 checked it; that report is also unverified.

Current status (as of September 2026): a paper claims the conjecture is proved, but the result remains unconfirmed; earlier published work retains sub-polylogarithmic losses.

Sources

ProofThis solution needs a summarySee full solutionHide full solution

Candidate proof checked by 5.6 Sol and Fable 5: https://github.com/DiarHaidary/nelson-nguyen-sparse-fock