32 problems

Valiant's conjecture. The permanent family $(\operatorname{perm}_n)$ does not admit circuits of polynomial size, equivalently,

Bounded-degree logarithmic-depth conjecture. For all sufficiently large $p$, there exists $c_p>0$, $\zeta>0$, and $\delta>0$ such that, if $D_n\leq\delta\log n$, then

Quantum spin-glass circuit-complexity conjecture. Near-ground states of quantum $p$-spin glasses cannot be prepared by polynomial-size circuits, even with arbitrary ancillas.

Fixed-average-degree NLTS conjecture. For all sufficiently large constant $\zeta$, the minimum circuit depth is in fact $\Omega(\log n)$.

Let $\textsf{NC}^{1}$ and $\textsf{P}$ denote the standard complexity classes of problems decidable by, respectively, poly-size Boolean circuits of logarithmic depth and polynomial…

Let $G$ be a finite solvable group, and consider the membership problem for $G$ in the Cayley table model, where the multiplication table of $G$ is given and the input specifies a…

Let $X$ be an $n\times n$ matrix of indeterminates, and let $I_n$ be the ideal generated by the $\tfrac{n}{2}\times\tfrac{n}{2}$ minors of $X$. For a nonzero polynomial $f\in I_n$,…

Let $\mathbb{F}$ be a field of characteristic zero, and let $f\in\mathbb{F}[x_1,\dots,x_n]$ be computed by an algebraic circuit of size $s$. A polynomial $g$ is a factor of $f$ if…

$\mathsf{TC}^0$–$\mathsf{NC}^1$ separation conjecture. $\mathsf{TC}^0\neq\mathsf{NC}^1$. Under this widely believed conjecture, chain-of-thought computation would extend the expres…

A quantum circuit family using unbounded quantum AND-gates and single-qubit gates is a QAC-circuit. The converse of the known simulation of quantum AND-gates by constant-depth circ…

Kush–Rossman's conjecture. The exponent $\frac{1}{3}\log_{\varphi} k\approx 0.49\log_2 k$ is optimal: no formulas of the relevant type and depth $O(\log k)$ can solve…

Sengupta–Venkateswaran conjecture. For certain non-monotone Boolean functions, the gap between their cancellative and non-cancellative circuit complexities is small.

NEXP circuit lower-bound consistency conjecture. The theory $\mathsf{V}^0_2$ is consistent with

Let $f$ be a Boolean function and let $\Omega$ be a Boolean circuit computing $f$. For each input node $x_i$, let $a_i$ be its valence, or fan-out, and define … Define $\gamma(f)$…

Let $\mathbf{A}$ be a finite nilpotent Maltsev algebra. A circuit $C_n(x_1,\ldots,x_n)$ is constant and absorbing when it is constant as a function and has the absorbing property;…

Let $G$ be a pattern graph. For each positive integer $n$, let $\mathrm{SUB}(G)$ denote the Boolean function on inputs encoding an $n$-vertex host graph $H$ whose vertices are colo…

Odd Alternating Cycle Conjecture. For every field $\mathbb{F}$ there exist $\varepsilon>0$ and an odd integer $\ell$ such that every $n$-vertex directed graph $G$ with

McKenzie's conjecture.

Barrington–Straubing–Thérien conjecture. There exists $q>0$ such that $C_n$ has size

Smolensky's conjecture. Such circuits cannot compute $\operatorname{MOD}_q$ in sub-exponential size.

Let $x\in\mathbb{F}_2^n$. In the systematic model, the data structure stores $r$ precomputed bits of $x$ together with additional stored bits, and a query algorithm answers each of…

Modified Euclidean continued-fraction conjecture. In this case, the resulting continued fraction $x=[b_1,\ldots,b_r]$ minimizes

Let $\mathbb{F}$ be a field. A digraph is an alternating odd cycle if its underlying undirected graph is a cycle and the orientations of its edges alternate with one exception. For…

For a Boolean function $f$, define its total influence by … A Boolean function $g$ $\epsilon$-approximates $f$ when $\mathbb E(f-g)^2\le\epsilon$. Low-influence approximation conje…

Let $f$ be a Boolean function, and let $M$ and $D$ denote the size and depth of a threshold circuit representing it. A circuit is monotone threshold when its threshold gates have n…