131 problems

Generalized Lax conjecture. All hyperbolicity cones are spectrahedral.

Goemans–Linial conjecture. The integrality gap satisfies

Let $E_2$ denote the second relaxation, or four-point bound, in the semidefinite hierarchy for energy minimization. For five particles on $S^2$, consider all completely monotonic p…

Consider the two-community stochastic block model with equal-sized communities and edge probabilities $p=\alpha\frac{\log n}{n}$ and $q=\beta\frac{\log n}{n}$, where $\alpha>\beta$…

A semi-algebraic set is a subset of $\mathbb R^n$ definable in the first-order structure $(\mathbb R;+,*)$. A set is semidefinite representable when it is primitive positive defina…

Let $\delta(m,n,r)$ denote the algebraic degree of semidefinite programming, and let the formula in Theorem be the formula established there under a stated restriction on the range…

Let $\delta(m,n,r)$ denote the algebraic degree of semidefinite programming, and let the formula in Theorem be the formula established there under its smoothness and range assumpti…

Rank-one optimal solution conjecture. If

Hypermetric integrality-gap conjecture. The integrality gap is still $2-o(1)$ when we impose the condition that the solution is a Hypermetric.

Let $G_n$ be the Schrijver graph, and let $G_n^{\boxtimes 2}$ denote its strong square. The Schrijver number of a graph $G$, denoted by $\vartheta'(G)$, is the corresponding streng…

Let $\mathcal{G}$ be a graph and let $k\geq 1$. The parameter $\theta_k(\mathcal{G})$ and the strengthened generalized $\vartheta$-number $\vartheta'_k(\mathcal{G})$ are defined as…

Consider the six semidefinite programs in Group II of Experiment II, namely 1dc1024, G40mb, hand, neosfbr25, r12000, and swissroll, and let $\sigma$ denote the ADMM penalty paramet…

Let $\overline{Z}$ be the final convergent point of the iterations of one-step ADMM. Let $\mathcal{C}(\overline{Z})$ be the cone used in the local second-order analysis, and let…

Let $\overline{Z}$ be a reference point, let $\mathcal{C}(\overline{Z})$ denote the cone appearing in the local second-order ADMM analysis, and let…

After introducing the inverse robustness variable $r$ and reformulating the radiotherapy-planning QCQP as a semidefinite-programming relaxation, the sandwiching algorithm can be ap…

Path-graph robustness conjecture. For all $n\geq 1$,

Let $G$ be an $n$-vertex graph, and let $\xi_f(G)$ denote the projective rank of $G$. Projective-rank energy conjecture. … This is proposed as a weakening of Fajtlowicz's graph ene…

Maximal-gamma conjecture. For every positive integer $\ell$, the maximum value of $\gamma_{\ell-1}(G,a)$ among $\ell$-minimal graphs is attained by a sparse stretched clique…

Enumeration conjecture. There are exactly $49$ non-isomorphic $3$-minimal graphs.

Mirka–Williamson conjecture. If a graph admits a unique partition corresponding to its maximum cut and the Goemans–Williamson relaxation on the graph is exact, then the rank-1 opti…

Let $\bm{w}$ and $\bm{w}_*$ denote points in the algorithm's variable space, let $F$ be the residual mapping, and let $\operatorname{dist}(\bm{w},\bm{w}_*)$ denote the distance bet…

Cohn–de Laat–Leijenhorst conjecture. Three-point semidefinite programming bounds prove that $C$ is a maximal spherical code.

Given an integer $\ell \geq 1$, let $n_+(\ell)$ be the smallest number of vertices of a graph with $\operatorname{LS}_+$-rank $\ell$. A graph $G$ is $\ell$-minimal if $r_+(G)=\ell$…

Spectrahedral-shadow representation conjecture. Every convex semialgebraic set is a spectrahedral shadow.

Fundamental limitation conjecture. This is a fundamental limitation of all methods using cheap linear bounds and branching.