The Hilbert-cube Overlap Gap Property conjecture for even p-spin tensors
The Hilbert-cube Overlap Gap Property conjecture for even p-spin tensors
Let and be independent random tensors in with independent entries distributed as , and set
with . For a domain , say that satisfies the Overlap Gap Property (OGP) with parameters and if every and every satisfying
obey
Hilbert-cube OGP conjecture. For every even , there exist and such that satisfies the OGP with domain , with probability at least for some and all sufficiently large . Furthermore, for every and every satisfying
one has with probability at least for some and all large . The OGP has already been proved for the binary domain ; the conjecture extends it to the Hilbert cube and is used as an assumption for the paper’s algorithmic barrier. The asserted chaos statement is included as part of the conjecture.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.