12 problems

Let $T$ be a tile in $\mathbb{Z}^n$. A tiling by translated copies of $T$ is periodic if it is invariant under a nonzero translation of $\mathbb{Z}^n$. Periodic tiling conjecture.…

For a fixed positive integer $k$, the $k$-polyomino tiling problem asks whether there is an algorithm deciding whether a set of $k$ polyominoes can tile the plane by translated cop…

Let $F$ be a number field, meaning a finite algebraic extension of $\mathbb{Q}$, and let $\mathcal{O}$ be a ring of algebraic integers. The Diophantine problem asks whether polynom…

An exponential Diophantine equation over $\mathbb Q$ is an equation built using variables, rational constants, arithmetic operations, and exponentiation with nonnegative base and e…

Tensor stable positivity conjecture. The set of yes-instances of tensor stable positivity, denoted $\textsc{tsp}$, is not recursively enumerable.

Asymptotic-capacity undecidability conjecture. The following problem is undecidable: given a partially fixed-size network $(V,E,\{A_v\},\{B_v\},s_M,s_E)$, decide whether its asympt…

A partially fixed-size network has vertex set $V$, edge set $E$, source-message sets $\\{A_v\\}$, demanded-message sets $\\{B_v\\}$, and size specifications $s_M$ and $s_E$. The sp…

Let $\mathcal{A}$ be an algorithm and $x$ an input. A $\otimes$-graph with cardinal inequalities is an $\otimes$-graph $\mathcal{G}$ equipped with cardinal inequalities between its…

Let $\mathcal{A}$ and $\mathcal{B}$ be automata, and let $\Sigma(\mathcal{A})$ and $\Sigma(\mathcal{B})$ be the automaton semigroups generated by their states. Their free product i…

Let $Y$ be a finite nonpositively curved square complex. A square complex is virtually special if it has a finite-sheeted cover that is special. Bridson–Wilton's conjecture. There…

Let $\mathcal D$ be a strongly regular event domain. A regular nice labeling is the labeling property used in Thiagarajan's conjecture. Undecidability conjecture. There does not ex…

For a finite set of permutation patterns $\mathcal{F}$, let $C_n(\mathcal{F})$ denote the number of permutations in $S_n$ avoiding all patterns in $\mathcal{F}$. Parity problem. Th…