47 problems

For every fixed planar graph $H$, Maximum Independent Set is solvable in polynomial time on the class of $H$-induced-minor-free graphs.

Let $E_n$ be the explicit family of $n$-dimensional ellipsoids considered in the cited problem, accessed through a membership oracle. Determine the quantum membership-query complex…

Fix $1<p<\infty$ and let $q=p/(p-1)$. Given a first-order local value--gradient oracle for an objective $f:\mathbb{R}^n\to\mathbb{R}$ whose gradient is $L$-Lipschitz from…

For every publicly computable function $H$ used in the Yamakawa–Zhandry quantum random-oracle certifiable-randomness protocol, every quantum prover that succeeds in the protocol mu…

Let $L$ be a computational problem, let $h(L)$ be its ordinary homological complexity, and let $h_q(L)$ be a proposed quantum homological complexity measure. Quantum homological co…

Let $k$ be a positive integer, and consider an instance of the two-variable linear system $2$-Lin-$k$ over $\mathbb{Z}_k$, with equations … An assignment is a map…

Let $A_1,B_1,C_1,A_2,B_2,C_2$ be finite-dimensional vector spaces over a field $\mathbb{K}$, and let $T_1\in A_1\otimes B_1\otimes C_1$ and $T_2\in A_2\otimes B_2\otimes C_2$. Thei…

Let $\mathrm{VBP}$ be the class of polynomial families computable by polynomial-size algebraic branching programs, and let $\mathrm{VNP}$ be Valiant's class of polynomially verifia…

Nisan–Szegedy's sensitivity conjecture. There exists an absolute constant $C>0$ such that, for every Boolean function $f$,

Complexity conjecture. For an appropriate purely combinatorial encoding of embedded shadows, the decision problem $\textnormal{\textsc{MinInflection}}$ for unrestricted shadows is…

Unpinning avoidance game complexity conjecture. The problem $\mathsf{Unpin_{AVOID}}(\Sigma,s)$ is $\textsf{PSPACE}$-complete for any $s$ and $\Sigma$, and…

Non-orientable surface complexity conjecture. Both $\mathsf{Pin}(\Sigma,s)$ and $\mathsf{SimplePin}(\Sigma,s)$ are in $\textsf{P}$ when $s\leq 3$, and are $\textsf{NP}$-complete wh…

Hardness-starts-at-four conjecture. For a fixed orientable surface $\Sigma$, the problem $\mathsf{SimplePin}(\Sigma,4)$ is $\textsf{NP}$-complete.

Let $[n]=\{1,\ldots,n\}$, let $\mathfrak{S}_n$ be the set of permutations of $[n]$, and let $\mathfrak{C}_n$ be the set of $n$-cycles in $\mathfrak{S}_n$. A join/union expression i…

Let $L$ be a physically realizable computation and let $h(L)$ denote its homological complexity. Homological Church–Turing thesis. Every physically realizable computation has finit…

Let $L$ be a decision problem in the bounded-error quantum polynomial-time class $\mathcal{BQP}$, and let $h(L)$ denote its homological complexity. Quantum homological obstruction…

Let $L$ be a computational problem with homological complexity $h(L)$. A physical system is said to solve $L$ efficiently when it computes solutions to $L$ within the relevant effi…

Let $M$ be a Boolean matrix, and let a monochromatic rectangle be a submatrix all of whose entries have the same value. Let ${\mathrm{r}}(M)$ denote the rank of $M$ over the reals,…

Let $d \geq 3$ and let $P$ be a lattice $d$-polytope. Lattice-polytope diameter conjecture. Computing a lattice diameter of $P$ is an $\operatorname{\mathsf{NP}}$-hard problem. Thi…

Let Feige's Hypothesis be the assertion that no efficient algorithm can prove the unsatisfiability of a random $3$-SAT formula with high probability, even when the formula has a sm…

Length-complexity conjecture. Let $f:\mathbb{N}\dashrightarrow\mathbb{N}$ be a partial recursive function. Given a Turing machine $\mathcal{G}$, for any $n\in\mathbb{N}$ let $T(n)$…

The bounded realization problem asks whether a valid realization exists subject to the specified bounds on the weights of the cycles. Bounded realization conjecture. The bounded re…

Let $\operatorname{sc}_{\mathrm{SchubertVanishing}}$ be the decision problem asking whether a Schubert coefficient vanishes. Schubert-vanishing hardness conjecture.…

Let $\operatorname{sc}_{\mathrm{SchubertVanishing}}$ be the decision problem asking whether a Schubert coefficient vanishes, for Schubert coefficients in the classical types $A$,…

Composition multiplicativity conjecture. For every $n,m\ge1$, there exists $k_0(n,m)\in\mathbb N$ such that, for every Boolean functions $f$ and $g$ on $n$ and $m$ bits, respective…