The Online Threshold for Contracting Hypergrid Vectors
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
The Johnson-Lindenstrauss lemma says a random projection nearly preserves lengths. “Nearly” leaves room: some vectors do get badly contracted, and with arbitrary real coordinates they are easy to find. Restrict the coordinates to a bounded integer grid and the problem gets interesting, with a wide gap between the vectors that exist and the vectors an efficient algorithm can find. The source charts that gap and a specific constant appears — \(\sqrt{\pi/8}\), the fixed point of a drift in the analysis of its own online algorithm. The conjecture is that this constant is not an artefact of one analysis but the truth: below it, no online algorithm succeeds.
View PDF · LaTeX source · Formal statement — not yet formalized
The problem (the source’s Definition 2). For \(n, m, B \in \mathbb{N}\) and \(\kappa \in \mathbb{R}_{>0}\) with \(m < n\), the contracting hypergrid vector (\(\mathrm{CHV}\)) problem with parameters \(n, m, B, \kappa\) is: given \(A \sim \mathcal{N}(0,1)^{m \times n}\), find \(x \in ([-B,B] \cap \mathbb{Z})^n\) with \(\|Ax\|_2 < \kappa\|x\|_2\sqrt{m}\). Write \(\alpha := m/n < 1\) for the aspect ratio. An algorithm is online if it processes the columns of \(A\) in sequence, fixing each entry of \(x\) before seeing the rest of the input.
Conjecture (the source’s Conjecture 1, “online threshold conjecture”). For every \(\delta\) and \(B\) there exists a sufficiently small \(\alpha\) and \(\epsilon\) so that every online algorithm fails to find \(x \in ([-B,B] \cap \mathbb{Z})^n\) such that \[\frac{\|Ax\|}{\sqrt{m}\,\|x\|} < \bigl(\sqrt{\pi/8} - \delta\bigr)\frac{\sqrt{\alpha}}{B}\] for at least an \(\epsilon\) fraction of \(\alpha n\) by \(n\) matrices \(A\), for all sufficiently large \(n\).
Where the constant comes from. Not from convenience. In the analysis of the source’s online algorithm a process \(U\) has drift pushing it toward a fixed point \(U = \frac{1}{2\mu} = \sqrt{\pi/8} \approx 0.627\), where \(\mu = \sqrt{2/\pi}\) is the mean of \(|\mathcal{N}|\). The conjecture asserts this fixed point is the genuine barrier for the whole class of online algorithms. That makes it a sharp-threshold claim rather than an order-of-magnitude one, and it is why a resolution has to control the constant and not merely the exponent.
The thresholds, for orientation.
| Quantity | Value |
|---|---|
| Statistical, \(\kappa_{\mathrm{stat}}\) | \(\Theta\bigl((2B+1)^{-1/\alpha}\bigr)\) |
| Computational, \(\kappa_{\mathrm{comp}}\) | \(\tilde{\Theta}\bigl(\sqrt{\alpha}/B\bigr)\) |
| Online algorithm achieves | \(O\bigl(\sqrt{\alpha}/B\bigr)\), when \(n \ge Km\log B\) |
| Both algorithms combined | \(O\bigl(\sqrt{\alpha}\log B/B\bigr)\), all \(n > m\) |
| Conjectured online barrier | \(\bigl(\sqrt{\pi/8}-\delta\bigr)\sqrt{\alpha}/B\) |
Any non-zero \(x\) achieves \(\kappa = \Theta(1)\) in expectation, so the question is how far down \(\kappa\) can be pushed. Above \(\kappa_{\mathrm{stat}}\) solutions exist; below it they do not.
The stability caveat is part of the claim. Immediately before stating the conjecture the source notes that its overlap-gap argument assumes the algorithm is committed to the approximate norm of the solution \(x\) before seeing \(A\), that its own online algorithm and those of Bansal and Spencer satisfy this, and that “We believe that some assumption of this type is necessary for an OGP-based argument to ensure stability.” Conjecture 1 as printed quantifies over “every online algorithm” without repeating that condition. This statement transcribes the conjecture as printed and flags the discrepancy rather than silently narrowing it; a resolution should say which reading it settles. A counterexample that is online but not norm-committed would be informative either way, and would bear directly on whether the assumption is necessary.
Two lower bounds, not comparable. The overlap-gap theorem gives evidence that \(\mathrm{CHV}\) is hard for \(\alpha \gg B^2\kappa^2\log(1/\kappa)\), against stable algorithms. The lattice-based theorem gives, under the worst-case polynomial hardness of standard lattice problems, that no polynomial-time algorithm solves \(\mathrm{CHV}\) for \(\kappa = O(1/(Bn^{1/2+\varepsilon}))\) — a statement about all efficient algorithms, but quantitatively weaker and over a more restricted range. The source records: “We leave it as a fascinating open question as to whether this lower bound can be improved to match that of Theorem 3 or similar.” That is a second open problem in the same paper and it is not this statement.
Sources
- Bogdanov, Rosen, Vafa and Vaikuntanathan. Adaptive Robustness of Hypergrid Johnson-Lindenstrauss. IACR ePrint 2025/666. The source. Definition 1 is on page 4 and Definition 2 on page 12; Theorem 2 and the informal conjecture are on page 6; Conjecture 1 is stated formally on page 16; Theorem 10 is on page 23.
- Bansal and Spencer. On-line Balancing of Random Inputs. Random Structures and Algorithms, 2020. The online discrepancy algorithm the source’s is a variant of, and whose guarantee matches the source’s at \(B = 1\).
- Gamarnik, Kızıldağ, Perkins and Xu. Algorithms and Barriers in the Symmetric Binary Perceptron Model. FOCS 2022. The overlap-gap bound that matches the source’s at \(B = 1\).
- Aubin, Perkins and Zdeborová. Storage Capacity in Symmetric Binary Perceptrons. Journal of Physics A, 2019. Introduces the Symmetric Binary Perceptron, the closest studied neighbour of \(\mathrm{CHV}\) and the subject of c/0095.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open. The upper side is proved and the lower side is proved only for stable algorithms and only up to constants.
What has to meet. The source’s online algorithm achieves \(O(\sqrt{\alpha}/B)\) and the conjecture forbids \((\sqrt{\pi/8}-\delta)\sqrt{\alpha}/B\). So the two sides differ by a constant factor, and closing the gap means making an OGP-style argument yield the exact drift fixed point rather than some constant times it. That is a stronger demand than the OGP method usually meets.
The mechanism behind the OGP evidence. The source’s Theorem 8 forbids configurations of \(r\) replicas with pairwise overlaps in a narrow band. Under the replica-symmetric model, solutions look like a product distribution with per-coordinate biases; a “bouquet” of vectors sharing their first \(t\) coordinates has overlaps concentrating near some \(1-\beta(t)\), and since \(\beta\) is \(O(1/n)\)-Lipschitz with \(\beta(0)\) bounded away from zero and \(\beta(n) = 0\), the intermediate value theorem forces the forbidden band to be hit. The source is candid that “it is difficult to justify the accuracy of the replica symmetric model, and algorithmic easiness may persist even under replica symmetry breaking.”
Checked against the literature, 2026-08-27. No resolution found. Targeted check on this line and the perceptron literature it cites, not an exhaustive sweep.
Why the gap is worth having. The source turns it into cryptography: from the hardness of \(\mathrm{CHV}\) it builds robust locality-sensitive hash functions for the Euclidean metric, which compress while preserving \(\ell_2\) distances up to a distortion no computationally bounded adversary can violate — even though violating inputs exist. Those imply collision resistance, so the statistical-computational gap yields cryptography beyond one-way functions.
Neighbouring problems this is not. In the Symmetric Binary Perceptron and the Nearest Boolean Vector problem the domain of \(x\) is \(\{-1,1\}^n\) rather than \(([-B,B]\cap\mathbb{Z})^n\), so \(\|x\|\) is fixed and \(x\) cannot have zero entries; and SBP bounds \(\|Ax\|_\infty\) rather than \(\|Ax\|_2\). At \(B = 1\) both the Bansal and Spencer algorithm and the Gamarnik–Kızıldağ–Perkins–Xu overlap-gap bound match the source’s, so \(B\) is the axis along which this statement is new.
What a reviewer should be suspicious of, in order. First, whether a claimed lower bound reaches the constant \(\sqrt{\pi/8}\) or only some constant — the whole content is the constant. Second, whether it applies to every online algorithm or only to norm-committed ones; see the caveat above. Third, whether a claimed algorithm is genuinely online, since the kernel-rounding algorithm is not and achieves a comparable \(\kappa\) by other means.