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

Let A(RN)pA\in(\mathbb{R}^N)^{\otimes p} have independent entries distributed as N(0,N(p1))\mathcal{N}(0,N^{-(p-1)}), and let BNHN\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 1exp(cN)1-\exp(-cN) for some c>0c>0 and all sufficiently large NN, every uHNu\in\mathcal{H}_N satisfying

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

also satisfies

minvBNuv2ϵ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.

Sources & referencesView supporting material

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.