Hardness conjecture for certifying lift-monotone properties of random regular graphs

Let $H$ be a $d$-regular multigraph on $k$ vertices, and let $\varepsilon>0$. Write $\mathcal{L}_{m}(H)$ for an $m$-sheeted lift of $H$. The operators $\mathcal{S}_{\varepsilon}^{\mathrm{rand}}$, $\widetilde{\mathcal{S}}_{\varepsilon}^{\mathrm{rand}}$, $\mathcal{S}_{\varepsilon}^{\mathrm{adv}}$, and $\widetilde{\mathcal{S}}_{\varepsilon}^{\mathrm{adv}}$ denote, respectively, random, respectful random, adversarial, and respectful adversarial noise as defined in the source. Let $\mathcal{G}(n,d)$ denote a uniformly random $d$-regular graph on $n$ vertices, and let $\mathcal{G}((\frac n2,\frac n2),d)$ denote the corresponding random bipartite $d$-regular graph. Hardness of detecting noisy lifts. If $H$ is Ramanujan, then there is no polynomial-time algorithm that achieves strong detection between $\mathcal{S}_{\varepsilon}^{\mathrm{rand}}\mathcal{L}_{m}(H)$ and $\mathcal{G}(n,d)$. The same holds when $\mathcal{S}_{\varepsilon}^{\mathrm{rand}}$ is replaced by any of $\widetilde{\mathcal{S}}_{\varepsilon}^{\mathrm{rand}}$, $\mathcal{S}_{\varepsilon}^{\mathrm{adv}}$, or $\widetilde{\mathcal{S}}_{\varepsilon}^{\mathrm{adv}}$. If $H$ is bipartite Ramanujan, then there is no polynomial-time algorithm that achieves strong detection between $\mathcal{S}_{\varepsilon}^{\mathrm{rand},\mathrm{bi}}\mathcal{L}_{m}(H)$ and $\mathcal{G}((\frac n2,\frac n2),d)$. The same holds when $\mathcal{S}_{\varepsilon}^{\mathrm{rand},\mathrm{bi}}$ is replaced by any of $\widetilde{\mathcal{S}}_{\varepsilon}^{\mathrm{rand},\mathrm{bi}}$, $\mathcal{S}_{\varepsilon}^{\mathrm{adv}}$, or $\widetilde{\mathcal{S}}_{\varepsilon}^{\mathrm{adv}}$. These conjectures are intended to imply hardness for certifying quantities that are lift-monotone, such as the independence number divided by the number of vertices, because such quantities can increase under graph lifts.