4 problems

Two-sided limiting-threshold conjecture. For every $epsilon>0$, there exists $kappa^*(epsilon)>0$ such that for every $kappalekappa^*(epsilon)$: no polynomial-time search algorithm…

Limiting $m$-OGP threshold conjecture. For every $epsilon>0$ and sufficiently small $kappa$, there do not exist polynomial-time algorithms for the SBP when…

Let $kappa>0$ and consider polynomial-time algorithms for finding solutions to the symmetric binary perceptron (SBP) at constraint density $alpha$. Bansal–Spencer optimality conjec…

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. T…