5 problems

AIM low-degree conjecture. In $G(n,\frac12)$, no degree-$o(\log^2 n)$ polynomial can find an independent set of size $0.9\log_2 n$.

Let $\mathbb P$ and $\mathbb Q$ be probability measures for a high-dimensional hypothesis-testing problem based on $\mathsf Y\in\mathbb R^N$, with $N=N_n$ and parameters scaling wi…

Let $\mathbb{G}(n,1/2)$ be the Erdős–Rényi random graph on $n$ vertices, and let a degree-$r$ polynomial algorithm mean a polynomial of degree at most $r$ used to find an independe…

Let $\mathbb{P}_n$ and $\mathbb{Q}_n$ denote a sequence of probability measures with sample space $\mathbb{R}^{n^k}$, where $k=O(1)$. Suppose that every polynomial $f$ of degree…

Low-degree polynomial threshold conjecture. Theorem (and Theorem) holds for all $\kappa > 1$.