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

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…