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_a\approx \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_{s\rightarrow\infty} \alpha_{ult_s} = \lim_{s\rightarrow\infty} \bar{\alpha}{ult_s} = \lim_{r\rightarrow\infty} \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.
