8 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…

Let $kappa>0$ and let the symmetric binary perceptron (SBP) have constraint density $alpha$. A search algorithm is stable when it satisfies the stability notion used in the paper.…

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…

Consider the symmetric binary perceptron (SBP) at a positive subcritical density, where its solution space consists mostly of totally frozen isolated solutions. A cluster is a coll…

Sharp phase-transition conjecture. There exists a critical density $alpha_c(kappa)$ such that the event $S_alpha(kappa)nevarnothing$ undergoes a sharp phase transition as $alpha$ c…

Let the symmetric binary perceptron (SBP) have constraint density $alpha$ and parameter $kappa>0$, and let the $m$-overlap-gap-property ($m$-OGP) threshold denote the density at wh…