Ultrametric OGP – parametric RDT emph{symmetric} binary perceptron connection

arXiv:2604.19712v1 Announce Type: cross
Abstract: In [97,99,100], an fl-RDT framework is introduced to characterize emph{statistical computational gaps} (SCGs). Studying emph{symmetric binary perceptrons} (SBPs), [100] obtained an emph{algorithmic} threshold estimate $alpha_aapprox alpha_c^{(7)}approx 1.6093$ at the 7th lifting level (for $kappa=1$ margin), closely approaching $1.58$ local entropy (LE) prediction [18].
In this paper, we further connect parametric RDT to overlap gap properties (OGPs), another key geometric feature of the solution space. Specifically, for any positive integer $s$, we consider $s$-level ultrametric OGPs ($ult_s$-OGPs) and rigorously upper-bound the associated constraint densities $alpha_{ult_s}$. To achieve this, we develop an analytical union-bounding program consisting of combinatorial and probabilistic components. By casting the combinatorial part as a convex problem and the probabilistic part as a nested integration, we conduct numerical evaluations and obtain that the tightest bounds at the first two levels, $bar{alpha}_{ult_1} approx 1.6578$ and $bar{alpha}_{ult_2} approx 1.6219$, closely approach the 3rd and 4th lifting level parametric RDT estimates, $alpha_c^{(3)} approx 1.6576$ and $alpha_c^{(4)} approx 1.6218$. We also observe excellent agreement across other key parameters, including overlap values and the relative sizes of ultrametric clusters.
Based on these observations, we propose several conjectures linking $ult$-OGP and parametric RDT. Specifically, we conjecture that algorithmic threshold $alpha_a=lim_{srightarrowinfty} alpha_{ult_s} = lim_{srightarrowinfty} bar{alpha}{ult_s} = lim_{rrightarrowinfty} alpha_{c}^{(r)}$, and $alpha_{ult_s} leq alpha_{c}^{(s+2)}$ (with possible equality for some (maybe even all) $s$). Finally, we discuss the potential existence of a full isomorphism connecting all key parameters of $ult$-OGP and parametric RDT.