14 problems

For $\theta\in[0,\pi/2]$, define $C_1$, $C_2$, and $\beta$ by … … where … Let $C_3,C_4,C_5,C_6$ be the matrices defined earlier in equation (CiEquations). Alternative six-matrix fe…

For each integer $m\geq 2$, consider the integer program $(\mathrm{CE})_m$ with variables $x\in\{0,1\}^{2m}$ and its linear relaxation. Let $x_m^\circ$ denote an optimal solution o…

Consider an instance of the multiple knapsack problem with compacity constraints, its linear relaxation $(\mathrm{mKPC})_{\mathrm{LP}}$, and its naive semidefinite relaxation. Writ…

Finite convergence conjecture. The hierarchy has finite convergence under the optimality condition assumptions.

Let $p$ be prime, let $G_p$ be the Paley graph, let $g$ be a multiplicative generator of $\mathbb F_p^\times$, and let $\vartheta$ denote the Lovász theta function. Improvement con…

Let $Q_r$ be the $r$-dimensional hypercube, let $\alpha_{\text{bal}}(Q_r)$ denote the maximum total size of a balanced bipartite biindependent pair in $Q_r$, and let $a(r)$ be the…

Tangential-direction conjecture.

Quantum speedup conjecture. A quantum speedup for semidefinite optimization should rely on techniques other than the direct quantization of a classical interior point method with l…

Let $p(G)$ be a graph parameter that is monotone nondecreasing under graph homomorphisms: whenever $T\to H$, one has $p(T)\leq p(H)$. For graphs $F$ and $G$, the categorical produc…

A nonlinearity interval is an interval of perturbation parameters on which the optimal set mapping exhibits nonlinear behavior; let a boundary point mean an endpoint of such an int…

${\rm LS}_+$-perfect graph conjecture. A graph $G$ is ${\rm LS}_+$-perfect if and only if

Let $G$ be a non-bipartite graph, and let $\mathcal{P}(\mathcal{S}_{r+}^n)$ denote its rank-restricted coordinate shadow at rank bound $r$. Tripartite closure conjecture. Tripartit…

Let a spectrahedral shadow be the affine projection of a spectrahedron, that is, a set of the form … where $F_k \in {\mathbb S}^m$ for $k=0,1,\ldots,n$ and $G_l \in {\mathbb S}^m$…

Common-solvability conjecture. The $k$ LMIs