14 problems

Let $D$ be a degree bound, and let $n$ denote the problem size. A robust algorithm is an algorithm whose running time is controlled up to polylogarithmic factors as described below…

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$.

Consider a hypothesis-testing problem with input size $N$ and testing advantage as the performance measure. Strengthened low-degree conjecture. Low-degree polynomials should perfor…

Low-degree conjecture. For suitably “nice” detection tasks, low-degree polynomials should match the power of all polynomial-time algorithms.

In the low-degree polynomial framework, estimators and test statistics are multivariate polynomials of degree at most $D$ in the observations; here $n$ denotes the problem size, an…

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…

Local algorithms, also known as factors of IID, produce solutions to random sparse instances of problems such as MaxCut and MaxSAT. Low-degree polynomials are a class of algorithms…

Let $d$ be a positive integer, and let a degree-$\leq d$ polynomial be chosen from the polynomial family considered in the paper. A function is a sumset extractor if it extracts fr…

Let the two distributions in a detection problem be given, and call a test statistic a low-degree polynomial if it is a polynomial of degree $O(\log n)$ in the underlying input var…

Let $D$ be a polynomial degree and let $n^{\tilde{\Theta}(D)}$ denote runtime up to poly-logarithmic factors in $n$. The degree-polynomial conjecture asserts that, for a broad clas…

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 conjecture. There is a test with runtime $n^{\tilde{O}(D)}$ and Type I + II error tending to zero if and only if there is a successful $D$-simple statistic for which

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

Consider a hypothesis-testing problem with null distribution $H_0$ and alternative distribution $H_1$, and let $D$ be a degree parameter. A $D$-simple statistic is a polynomial $f$…