  We study tetrahedron maps, which are set-theoretical solutions to the
Zamolodchikov tetrahedron equation, and Yang-Baxter maps, which are
set-theoretical solutions to the quantum Yang-Baxter equation.
  In particular, we clarify the structure of the nonlinear algebraic relations
which define linear (parametric) tetrahedron maps (with nonlinear dependence on
parameters), and we present several transformations which allow one to obtain
new such maps from known ones. Furthermore, we prove that the differential of a
(nonlinear) tetrahedron map on a manifold is a tetrahedron map as well. Similar
results on the differentials of Yang-Baxter and entwining Yang-Baxter maps are
also presented.
  Using the obtained general results, we construct new examples of (parametric)
Yang-Baxter and tetrahedron maps. The considered examples include maps
associated with integrable systems and matrix groups. In particular, we obtain
a parametric family of new linear tetrahedron maps, which are linear
approximations for the nonlinear tetrahedron map constructed by Dimakis and
M\"uller-Hoissen [arXiv:1708.05694] in a study of soliton solutions of vector
Kadomtsev-Petviashvili (KP) equations. Also, we present invariants for this
nonlinear tetrahedron map.
