379 problems

Hendrych's NP-hardness conjecture. The Bayesian AOD problem is NP-hard. This conjecture is resolved in the source: the paper proves NP-hardness for its regularized A-optimal design…

The Fooling-Set-Submatrix problem takes integers $n,m$ and an $m\times m$ $0/1$-matrix $A$ as input, and asks whether $A$ contains a fooling-set submatrix of size $n$. NP-hardness…

Let $p,q$ be positive integers with $p\geq 1$ and $q\geq 2$, and let $i\leq p$ and $j\leq q$. Let $\Psi$ be a family of graphs for which recognizing generating subgraphs isomorphic…

Let $\omega$ denote the exponent of matrix multiplication, equivalently the asymptotic exponent governing the border rank of the matrix multiplication tensors. Exponent-two conject…

For a fixed integer $k\ge 0$, given a planar graph $G$, decide whether there exists a family of pairwise interiorly disjoint, non-self-intersecting grid paths $(P_v)_{v\in V(G)}$ s…

Given an approval profile $P$ and a target committee size $k$, determine whether there exists a polynomial-time algorithm that outputs a committee $W$ of size $k$ satisfying both j…

Let $X$ be a set of $T$ instances equipped with an unknown total order $\prec$, and let $\mathcal{C}_{\prec}$ be the class of threshold concepts whose positive sets are prefixes of…

Given a finite simple unweighted graph $G=(V,E)$, decide whether the standard Goemans–Williamson semidefinite relaxation of Max-Cut has the same optimal value as the integer Max-Cu…

Given a weighted graph $G=(V,E,w)$, where $w:E\to\mathbb{R}_{\ge 0}$, find an integral cycle basis $\mathcal{B}$ minimizing its total weight…

Conjecture: For every quantum polynomial-time sampler $S$ and every classical string $x$ that $S$ outputs with probability $\delta$, there is a quantum program for $x$ of length at…

Given a digraph $D=(V,A)$, determine whether there is a partition $A=A_1\mathbin{\dot\cup}A_2$ such that one of the following holds: (i) $D[A_1]$ is a perfect matching and $D[A_2]$…

For a field $F$ of characteristic zero, let $\operatorname{Imm}_{(2^m)}(X)=\sum_{\sigma\in S_{2m}}\chi_{(2^m)}(\sigma)\prod_{i=1}^{2m}x_{i,\sigma(i)}$, where $\chi_{(2^m)}$ is the…

For each fixed rational $p\in(1,\infty)$, given vectors $v_1,\ldots,v_m\in\mathbb{Q}^d$ defining the zonotope $Z=\left\{\sum_{i=1}^m\lambda_i v_i: -1\leq\lambda_i\leq 1\right\}$, d…

Let $G=(V,E)$ be a simple graph, directed or undirected, with positive real-valued edge weights, and let $s,t\in V$. When the graph is accessed through vertex and incident-edge que…

Feder–Vardi dichotomy conjecture. For any relational structure $T$, $\textsc{Csp}(T)$ is either NP-complete or polynomial-time solvable.

Quantum supremacy conjecture. There is no classical randomized algorithm that performs RCS to inverse-polynomial total variation-distance error.

Hardness conjecture for the discrete iteration problem. Given $a$ and $a^n$, it is computationally hard to recover $n$ for general parameter values, input vectors, and sufficiently…

Determine whether there exists a purely combinatorial algorithm for boolean matrix multiplication running in time O(n^{2+o(1)}) without using algebraic Strassen-like tensor methods…

Determine whether Condon's simple stochastic games can be solved in polynomial time: given a two-player zero-sum turn-based stochastic game with binary decisions, rational transiti…

Determine whether there exists a uniform deterministic comparison-based algorithm that, for every connected undirected graph with n vertices and m edges carrying distinct real-valu…

Determine whether the unique solution of every linear complementarity problem with a rational P-matrix and rational right-hand side can be computed in time polynomial in the bit le…

Let OPT(G,k)=max{S subseteq V(G), |S|=k}|E(G[S])| for a finite simple undirected input graph G. Prove or refute the assertion that there exists an absolute constant epsilon0 for wh…

Prove or refute that for every epsilon 0 there is no randomized algorithm which, given an n by n Boolean matrix and then n Boolean query vectors one at a time, outputs each Boolean…

For each integer n=2, let CDFT(n) be the minimum number of steps needed to compute every output of the unnormalized complex DFT yj=sum(l=0)^(n-1) exp(-2piijl/n)xl, 0<=j<n. Initiall…

Prove that there is a universal constant C such that, for every access sequence, the cost of the splay-tree algorithm is at most C times the minimum cost of any offline dynamic bin…