8 problems

Let $p$ be a polynomial hyperbolic with respect to $e\in \mathbb{R}^n$, and let $\Lambda_+(p,e)$ denote its hyperbolicity cone. A polynomial has a definite determinantal representa…

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…

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…

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

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