123 problems

Let an instance of the Unique Games Problem consist of a graph, a set of colors, and a matching of the colors for each edge. The value of an instance is the largest fraction of edg…

Mulmuley's conjecture. These constants belong to $\#\mathsf{P}$.

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 $F_2$ be the free group of rank two, and consider the power word problem allowing nested exponents. For a fixed constant nesting depth, write…

Complete-graph degree sequence optimization conjecture. The line sum problem over $H=K_{m,n}$, as well as the degree sequence optimization problem over $H=K_n$, is polynomial-time…

Let $\mathcal{T}$ be the class of theories considered in the source, and let $\mathsf{TFNP}(T)$ and $\mathsf{TFNP}^*(T)$ denote the corresponding classes associated with…

Let $d\ge 2$ and consider a synchronous robotic network in $\mathbb{R}^d$ using the circumcenter control law. Write $\mathcal{T}_{\textup{rndzvs}}$ for the rendezvous task and…

Let $k$ be a field, and let $\omega$ be the smallest exponent such that linear algebra on square $n\times n$ matrices over $k$ has complexity $O(n^{\omega+\epsilon})$ for every…

Let $G,H\subset S^3$ be spatial graphs, let $G\circ H$ denote their loop sum, and let $tp(G)$ denote the three-page complexity of a spatial graph. Three-page complexity additivity…

Let $S(p,q)$ be the non-oriented $2$-bridge link with parameters $p,q\geq 1$, and let $tp(G)$ denote the minimal value of $ar(G)-2$ over all general three-page embeddings of a spat…

A linear programming instance is specified by rational data, and an algorithm is strongly polynomial if its number of arithmetic operations and the sizes of the intermediate number…

Linear-complexity conjecture. The computation of an slp representation of any geometric object associated to the polynomial family should have complexity linear in both $D$ and $L$…

PakPanova's conjecture. Counting contingency tables of non-fixed sizes from unary input is $\#\mathsf{P}$-complete.

Pak's conjecture. Under standard complexity-theoretic assumptions, the Kronecker coefficients do not belong to $\#\mathsf{P}$ and therefore do not have a nice positive combinatoria…

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

Let $\mathrm{BPP}$ denote the class of decision problems solvable by probabilistic classical algorithms in bounded-error polynomial time, and let $\mathrm{BQP}$ denote the class so…

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.

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 $[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…

Online Matrix–Vector conjecture. Computing $\mathbf{A}\boldsymbol{x}$ for general matrices cannot be done in truly sub-$mn$ time per multiplication.

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