Ultrametric OGP - parametric RDT symmetric binary perceptron connection

arXiv:2604.19712v1 Announce Type: new Abstract: In [97,99,100], an fl-RDT framework is introduced to characterize statistical computational gaps (SCGs). Studying symmetric binary perceptrons (SBPs), [100] obtained an 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, ar{alpha}{ult_1} approx 1.6578 and ar{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} ar{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.

Source: arXiv cs.LG | 2026-04-22

Related