8 problems

Let $c_{i,j}$, for $i,j\in [n]$, be independent identically distributed positive random variables, and let $A_n$ be the minimum total cost of assigning $n$ faculty to $n$ slots, wi…

Assume the setup of the paper's fl-RDT theorem, including the quantities $\psi_{rp}$, $\psi_{rd}$, $\hat{\mathbf p}$, $\hat{\mathbf q}$, and $\hat{\mathbf c}$. Define the algorithm…

Let $G\nin\mathbb{R}^{m\times n}$ have independent standard-normal entries. For constraint density $\alpha=\lim_{n\to\infty}m/n$ and $\kappa\in\mathbb{R}_+$, consider the statistic…

Consider structured random combinatorial optimization problems whose instances exhibit phase transitions, including random $K$-SAT. Phase-transition hardness conjecture. The source…

Variational-principle conjecture. The variational principle describing the admissible values $(\kappa,M/N)$ and the radius $\bar{q}$ is deeply related to the geometry of the soluti…

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

Let ${\cal E}$ be the dimensionless ground-state energy, let ${\cal E}^{(typ)}=-\sqrt{1+\Gamma}$ be its typical value, and let ${\cal E}_c=-\sqrt{\frac{1+2\Gamma}{1+\Gamma}}$ be th…

Consider a random combinatorial optimization problem of size $n$, with feasible solutions ${\mathbf x}=(x_i,1\leq i\leq n)$, objective function $f({\mathbf x})$, optimal solution…