Near-optimal Hilbert-cube points are close to binary points

About 7 years old · traced to

Let A∈(RN)⊗pA\in(\mathbb{R}^N)^{\otimes p} have independent entries distributed as N(0,N−(p−1))\mathcal{N}(0,N^{-(p-1)}), and let BN⊂HN\mathcal{B}_N\subset\mathcal{H}_N denote the binary and Hilbert-cube domains used for the p-spin model. Hilbert-cube localization conjecture. For every ϵ>0\epsilon>0, there exists δ>0\delta>0 such that, with probability at least 1−exp⁡(−cN)1-\exp(-cN) for some c>0c>0 and all sufficiently large NN, every u∈HNu\in\mathcal{H}_N satisfying

A(u)/N≤(1−δ)E[ηN]A(u)/N\leq(1-\delta)\mathbb{E}[\eta_N]

also satisfies

min⁡v∈BN∥u−v∥2≤ϵN.\min_{v\in\mathcal{B}_N}\|u-v\|_2\leq\epsilon\sqrt{N}.

If true, this would reduce the conjectured OGP for near-optimal points in the Hilbert cube to the established binary-domain OGP; the paper explicitly presents it as an interesting open problem.

References

Primary source

David Gamarnik and Aukosh Jagannath, “The Overlap Gap Property and Approximate Message Passing Algorithms for p-spin models”, arXiv:1911.06943 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.