  In this paper we study colorings (or tilings) of the two-dimensional grid
$\mathbb{Z}^2$. A coloring is said to be valid with respect to a set $P$ of
$n\times m$ rectangular patterns if all $n\times m$ sub-patterns of the
coloring are in $P$. A coloring $c$ is said to be of low complexity with
respect to a rectangle if there exist $m,n\in\mathbb{N}$ and a set $P$ of
$n\times m$ rectangular patterns such that $c$ is valid with respect to $P$ and
$|P|\leq nm$. Open since it was stated in 1997, Nivat's conjecture states that
such a coloring is necessarily periodic. If Nivat's conjecture is true, all
valid colorings with respect to $P$ such that $|P|\leq mn$ must be periodic. We
prove that there exists at least one periodic coloring among the valid ones. We
use this result to investigate the tiling problem, also known as the domino
problem, which is well known to be undecidable in its full generality. However,
we show that it is decidable in the low-complexity setting. Then, we use our
result to show that Nivat's conjecture holds for uniformly recurrent
configurations. These results also extend to other convex shapes in place of
the rectangle.\\ After that, we prove that the $nm$ bound is multiplicatively
optimal for the decidability of the domino problem, as for all $\varepsilon>0$
it is undecidable to determine if there exists a valid coloring for a given
$m,n\in \mathbb{N}$ and set of rectangular patterns $P$ of size $n\times m$
such that $|P|\leq (1+\varepsilon)nm$. We prove a slightly better bound in the
case where $m=n$, as well as constructing aperiodic SFTs of pretty low
complexity.\\ This paper is an extended version of a paper published in STACS
2020.
