25 problems

Low-degree conjecture. If there exist $\epsilon>0$ and $D=D(n)\geq (\log n)^{1+\epsilon}$ such that

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…

Let $\bW \in \mathbb{R}^{n \times n}_{\mathrm{sym}}$ be drawn from the Gaussian orthogonal ensemble, and let $\lambda^+(\bW)$ denote the non-negative principal component analysis o…

Let planted dense subgraph use constant edge densities $0<q<p\le1$, with a denser planted subgraph inside a background random graph. Planted Dense Subgraph Hardness Conjecture. All…

Average-case complexity conjecture. The average case complexity of $\app$ in $\lstd$ is of the same order as the average case complexity of $\app$ in $\lall$.

Let $F=F_n$ be a free group of rank $n$, and let $NMin_l\subset F$ be the set of all non-minimal elements of length $l$. Let $LR(w)$ denote the length-reducing complexity associate…

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…

Stable-algorithm optimality conjecture. The failure of stable algorithms should delineate the true computational hardness threshold of a problem.

Let $\Delta$ denote the degree of a random regular graph, and consider efficient algorithms for finding proper colorings of such graphs. Algorithmic threshold conjecture. No effici…

For a random Gaussian matrix $\mathbf{A}\sim\mathcal{N}(0,1)^{n\times m}$ with $m\geq n$, let $\mathrm{SBP}_{\kappa}$ ask for a vector $\mathbf{x}\in\{-1,1\}^m$ satisfying … Here…

Let $k>r$ be constants, let $Q$ be any distribution over $k$-clauses with $N$ variables and complexity $r$, and let $0<\eta<1$. Define the noisy planted distribution by … where…

Let ${\cal G}_{n,\delta}$ denote the Erdős–Rényi random graph model with edge probability $\delta$, and let $(K_n,\lambda)$ be a random simple temporal graph. A $\delta$-clique is…

Let angular synchronization be the problem of estimating vertex phases from noisy pairwise angular measurements, and suppose the noise is Gaussian. Approximate message-passing opti…

Let $k$ be fixed and let a random $k$-SAT formula have clause density $alpha$. The value $(1+o_k(1))2^k\ln k/k$ is the clustering threshold described in the paper. Algorithmic thre…

Let two correlated Erdős–Rényi graphs on $n$ vertices have edge correlation coefficient $\rho_\mathrm{u}$. Exact recovery means finding the vertex correspondence between the graphs…

Let $G(n,d/n)$ be the sparse Erdős–Rényi random graph with fixed, sufficiently large $d$, and define the density of an independent set to be its size divided by the number of verti…

Let $G(n,1/2)$ be the Erdős–Rényi random graph, and let an independent set be a set of vertices containing no edge. Here, $\log_2 n$ denotes the base-two logarithm, and “with high…

In the $(k,N,r)$-SUM problem, the input consists of $r$ elements $z_1,\ldots,z_r$, independently and uniformly chosen from $\{-N,\ldots,N\}$. The goal is to find an ordered $k$-tup…

Number-partitioning hardness conjecture. The problem is algorithmically hard for objective values smaller than order

Consider the original random matrix discrepancy model and its planted counterpart, in which a matrix $A$ is generated from the Bernoulli ensemble conditioned on a particular vector…

Fix constants $\gamma > 0$, $\beta > -1$, and $\rho \in (0,1)$. Let $N=N(n)$ satisfy $n/N \to \gamma$ as $n \to \infty$. In the spiked Wishart model, under $\mathbb{Q}$ the observa…

Let $\Omega$ be finite or $\mathbb R$, let $k$ be fixed, and let $N=\binom nk$. Let $\nu$ be a product distribution on $\Omega^N$, let $\mu$ be another distribution on $\Omega^N$,…

Let $m$ and $n$ be polynomial in one another. The problems $k\textsc{-pc}(n,k,1/2)$, $\textsc{bpc}(m,n,k_m,k_n,1/2)$, $k\textsc{-bpc}(m,n,k_m,k_n,1/2)$, and…

Let $\rho$ be a distribution on $k$-subsets of $[n]$, and let $p_\rho(s)=\mathbb P_{S,S'\sim\rho^{\otimes 2}}[|S\cap S'|=s]$ be the intersection-size probability mass function. Let…

For an average-case problem, consider algorithms based on the Kikuchi free energy and algorithms based on the sum-of-squares hierarchy. Kikuchi free-energy optimality conjecture. F…