23 problems

OGP computational-hardness conjecture. OGP is a marker of computational hardness: instances with the OGP cannot be solved efficiently by the relevant algorithmic classes.

Average-case collision-hardness conjecture. Finding one of these collisions is algorithmically hard in the average case.

Collision-finding hardness conjecture. In the regime where collisions exist and the collision solution space has the OGP, finding collisions with $|q_1|<1$ is infeasible.

Consider the submatrix problem in which one seeks a submatrix with average value $\alpha\sqrt{(2\log N)/k}$, where $\alpha^*=5\sqrt{2}/(3\sqrt{3})\approx 1.36$ is the overlap-gap t…

Let $\mathcal{M}\in\mathbb{R}^{M\times n}$ have i.i.d. Rademacher or $\operatorname{Bernoulli}(p)$ entries, and let $n=\Theta(M\log M)$. Consider the set of solutions with constant…

Let $\eta_{\rm p,OGP}$ denote the OGP barrier value for the spherical spin model, and let Langevin dynamics be run for $N^{O(1)}$ time. Langevin dynamics conjecture. A natural conj…

Two-sided limiting-threshold conjecture. For every $epsilon>0$, there exists $kappa^*(epsilon)>0$ such that for every $kappalekappa^*(epsilon)$: no polynomial-time search algorithm…

Limiting $m$-OGP threshold conjecture. For every $epsilon>0$ and sufficiently small $kappa$, there do not exist polynomial-time algorithms for the SBP when…

Let $kappa>0$ and consider polynomial-time algorithms for finding solutions to the symmetric binary perceptron (SBP) at constraint density $alpha$. Bansal–Spencer optimality conjec…

Let $kappa>0$ be the SBP parameter and let the algorithmic threshold be the largest constraint density up to which efficient algorithms can find a solution with high probability. T…

Let the symmetric binary perceptron (SBP) have constraint density $alpha$ and parameter $kappa>0$, and let the $m$-overlap-gap-property ($m$-OGP) threshold denote the density at wh…

Symmetric-perceptron hardness conjecture. In this regime, finding a solution $\sigma$ is hard, and the OGP method should rule out classes of algorithms such as low-degree-polynomia…

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

Let $R$ satisfy … For every $\epsilon>0$, let $C=C(\epsilon)$ be a constant. Here $k$, $n_{\mathrm{pos}}$, $p'$, and the profile $\phi(\ell)$, as well as the first moment function…

Consider a random optimization problem whose near-optimal solution space has the Overlap Gap Property (OGP): near-optimal solutions split into regions with an interval of normalize…

Let $A\in(\mathbb{R}^N)^{\otimes p}$ have independent entries distributed as $\mathcal{N}(0,N^{-(p-1)})$, and let $\mathcal{B}_N\subset\mathcal{H}_N$ denote the binary and Hilbert-…

Hilbert-cube OGP conjecture. For every even $p\geq4$, there exist $\mu>0$ and $0<\nu_1<\nu_2<1$ such that $\mathcal{A}$ satisfies the OGP with domain $\mathcal{S}_N=\mathcal{H}_N$,…

Landscape conjecture. Suppose … If $k=o(\sqrt n)$, then:

OGP phase-transition conjecture. The onset of the phase transition for the presence of OGP should coincide with the onset of algorithmic hardness.

Consider sparse linear regression with $n$ observations and sparsity level $k$, and let the algorithmic sample-size scale be $n_{\mathrm{alg}}=k\log p$. The Gamarnik–Zadik absence-…

Let $\beta^*$ be an exactly $k$-sparse vector with $|\beta^*|_{\mathrm{min}}\geq 1$, and consider the near-optimal sparse regression solutions whose objective is the residual norm…

Let $\alpha^*=5\sqrt{2}/(3\sqrt{3})$ denote the threshold obtained from pairwise overlap analysis of $k\times k$ submatrices of an $n\times n$ Gaussian random matrix. Consider exte…

Let $A$ be an $n\times n$ matrix with independent standard Gaussian entries, and let $k$ be a growing function of $n$. For a fixed $\alpha\in[1,\sqrt{2}]$, consider finding a…