2 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$ 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…