5 problems

Solution-space shattering conjecture. The solution-space shattering brought by XORs might be the reason for the weakness of local-search solvers in handling XORs.

Let $R$ satisfy … For every $\epsilon>0$, let $C=C(\epsilon)$ be a constant. Here $k$, $n_{\mathrm{pos}}$, $p'$, and the profile $\phi(\ell)$, as well as the first moment function…

The paper considers a distribution of the form $p(x)\propto e^{-f(x)}$, where $f$ is close to a mixture of log-concave functions in the sense that there exists…

Diamond-cactus local-search conjecture. This algorithm gives a better-than-$4/9$ approximation for MPS.

Triangle-and-diamond local-search conjecture. Whenever such a move is possible, performing it yields a local-search algorithm that breaks the $1/6$-approximation barrier for MPT, a…