Bounded-norm bipartite Johnson-Lindenstrauss reduction
Conjecture 2.4 · arXiv:1610.00239
Status open medium confidence
Conjecture 2.4 from arXiv:1610.00239 asserts that the bipartite Johnson-Lindenstrauss reduction to dimension $t = \lfloor C\log(2+\varepsilon^2 n)/\varepsilon^2 \rfloor$ can be achieved with the additional guarantee that all output vectors have Euclidean norm at most $O(1)$. No resolution or significant partial progress has been found in the literature as of May 2026. The conjecture has been open since 2017; if proved it would close the gap in the space complexity bounds of Theorem 2.2 for $\varepsilon \geq 2/\sqrt{n}$.
Reviewer notes. No follow-up paper addressing Conjecture 2.4 was found across three targeted searches. The conjecture is roughly 9 years old; the medium confidence reflects that this age makes pure absence of indexed results somewhat less conclusive than for a very recent paper.
Context
Theorem 1.2 establishes a bipartite Johnson-Lindenstrauss reduction to dimension $t = \lfloor C\log(2+\varepsilon^2 n)/\varepsilon^2 \rfloor$ that approximates inner products up to additive error $\varepsilon$, but does not control the norms of the output vectors. The authors conjecture that the output vectors can simultaneously be taken to have bounded Euclidean norm $O(1)$. If true, this would close the gap between the upper and lower bounds in the first bullet of Theorem 2.2 for all $\varepsilon \geq 2/\sqrt{n}$.
Notes. PDF source — norm notation $\|\cdot\|$ appears as bare vertical bars in the raw extract; reconstructed from context. The paper proves two partial results supporting the conjecture: the case $t = \Omega(n)$ (i.e., $\varepsilon = \Theta(1/\sqrt{n})$) is established as Theorem 2.5, and a matching bit-count estimate is proved for the column-query variant.
Source paper
Optimal compression of approximate inner products and dimension reduction
Noga Alon, Bo'az Klartag · 2017-04-02
https://arxiv.org/abs/1610.00239
PDF source