35 problems

Planted Boolean Vector SoS conjecture. Theorem $$ holds with the bound on the dimension $p$ of a random subspace loosened to

Let $V$ be the variety under consideration, let its RR discriminant be defined by a polynomial, and call a factor isotropic when it belongs to the isotropic part of that discrimina…

De Klerk–Pasechnik conjecture. For every non-empty graph $G$,

Collins–Dykema–Torres-Ayala conjecture. This coefficient is non-negative.

Let $\mathsf{M}(\bm W)$ denote the Sherrington–Kirkpatrick Hamiltonian instance with random matrix $\bm W$, and let $c(\bm W)$ be the approximation ratio certified by an algorithm.…

Let $obreak\forall obreak\text{?}$ For every $obreak\text{?}$

Let a biquadratic form be a homogeneous polynomial of degree two in each of two variable vectors, and let its SOS rank be the smallest number of squares of bilinear forms in a sum-…

Let $P(\mathbf{x},\mathbf{y})$ be a $3 \times 3$ symmetric PSD biquadratic form, so $P(\mathbf{x},\mathbf{y})\geq 0$ for all $\mathbf{x},\mathbf{y}\in\mathbb{R}^3$. A bilinear form…

Let $\mathcal{A}$ be a symmetric $\mathrm{B}_{0}$-biquadratic tensor, meaning a symmetric biquadratic tensor satisfying the $\mathrm{B}_{0}$ conditions specified in the source. An…

Let $\mathcal{A}$ be a symmetric biquadratic M-tensor: a symmetric biquadratic tensor that can be written as $\mathcal{A}=\alpha\mathcal{I}-\mathcal{B}$, where $\mathcal{I}$ is the…

Fix $1<\alpha<2$, set $T=N^\alpha$, and let $M_{ran}$ be a random $T\times N$ Gaussian matrix. Let $v\in\mathbb R^N$ satisfy $\|v\|_\infty\leq1$, and suppose…

Let $X$ and $Y$ be arbitrary real Toeplitz matrices, let $\langle X,Y\rangle$ denote their Frobenius inner product, and let $\|\cdot\|$ denote the Frobenius norm. Lu–Wenzel conject…

Let $\Gamma_{n,d}$ be the class of symmetric degree-$d$ polynomials in $n$ variables. For a symmetric hyperbolic polynomial $p$, let its associated operator be the operator defined…

Let $\Gamma_{n,d}$ denote the class of symmetric degree-$d$ polynomials in $n$ variables, and let $\Delta_{\vec{1},\vec{1}}p$ be the indicated second directional derivative. A poly…

Let $G$ be a graph with stability number $\alpha(G)$, and let $A_G$, $I$, and $J$ denote its adjacency, identity, and all-ones matrices, respectively. Define … By the Motzkin–Strau…

Rank-separation conjecture. There exist no functions $f,g,h\colon\mathbb{N}\to\mathbb{N}$ such that, for every $p\in\mathbb{R}[x,y]$, independently of the degree of $p$,

Finite-convergence conjecture. For any graph $G$,

Pseudodistribution product inequality.

Random-regular-graph MaxCut conjecture. For some $\delta>0$, with high probability there is a degree-$n^\delta$ pseudoexpectation operator $\widetilde{\mathop{\varmathbb{E}}}$ on B…

Planted Affine Planes SoS conjecture. Theorem $$ holds with the bound on the number of sampled vectors loosened to

Consider a broad class of hypothesis-testing problems $H_0$ versus $H_1$. A polynomial $f$ is a $D$-simple statistic if it has degree at most $D$ and satisfies … while…

Let $\delta \in (0,1)$, and let $\bm{M}^{(\delta)}$ be the Montanari–Sen witness. Fix $d \in 2\mathbb{N}$, and choose constants $\sigma_k^2$ depending only on $\delta$. Let…

Let $\alpha,\delta \in (0,1)$ and let $d \in 2\mathbb{N}$. The random matrix $\bm{M}^{(\alpha,\delta)}(\bm{W})$ is the proposed degree-$d$ witness, and $\mathscr{E}_d^N$ is the deg…

Let $\mathcal{G}$ and $\mathcal{H}$ be the graph objects used in the paper's polynomial model, with vertex sets $V(\mathcal{G})$ and $V(\mathcal{H})$, parameters $n_\mathcal{G}$ an…

Sum-of-squares representation conjecture. A generic quadratic form nonnegative on $X$ has exactly