Tilde-theta algorithmic-threshold conjecture for the symmetric binary perceptron

Let $\kappa>0$ be the SBP parameter and let the algorithmic threshold be the largest constraint density up to which efficient algorithms can find a solution with high probability. Tilde-theta threshold conjecture. As $\kappa\to0$, the algorithmic threshold for the SBP is at

$$\widetilde{\Theta}(\kappa^2).$$

The paper establishes an $m$-OGP obstruction at densities of order $\kappa^2\log_2(1/\kappa)$ and an efficient algorithm at densities of order $\kappa^2$, leaving only polylogarithmic factors between the known bounds.