5 problems

Consider the $p$-spin model and stable algorithms for its optimization problem. For $p\geq 4$ even, the largest value achievable by stable algorithms is strictly sub-optimal. All-…

Let $c_{K,\rm SAT}$ denote the phase-transition point corresponding to the satisfiability threshold in the random $K$-SAT model. Random K-SAT hardness-location conjecture. Hard ins…

Frozen-variable conjecture. The emergence of frozen variables is the primary cause of algorithmic hardness in random $K$-SAT; moreover, the Backtracking Survey Propagation algorith…

OGP phase-transition conjecture. The onset of the phase transition for the presence of OGP should coincide with the onset of algorithmic hardness.

A constraint satisfaction problem instance has frozen solutions when some variables cannot be changed within the solution structure, while a solution is unfrozen when no such freez…