  We consider the approximability of constraint satisfaction problems in the
streaming setting. For every constraint satisfaction problem (CSP) on $n$
variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the
trivial approximability by a factor of $q$ requires $\Omega(n)$ space even on
instances with $O(n)$ constraints. We also identify a broad subclass of
problems for which any improvement over the trivial approximability requires
$\Omega(n)$ space. The key technical core is an optimal,
$q^{-(k-1)}$-inapproximability for the \textsf{Max $k$-LIN}-$\bmod\; q$
problem, which is the Max CSP problem where every constraint is given by a
system of $k-1$ linear equations $\bmod\; q$ over $k$ variables. Our work
builds on and extends the breakthrough work of Kapralov and Krachun (Proc. STOC
2019) who showed a linear lower bound on any non-trivial approximation of the
MaxCut problem in graphs. MaxCut corresponds roughly to the case of \textsf{Max
$k$-LIN}-$\bmod\; q$ with ${k=q=2}$. For general CSPs in the streaming setting,
prior results only yielded $\Omega(\sqrt{n})$ space bounds. In particular no
linear space lower bound was known for an approximation factor less than $1/2$
for {\em any} CSP. Extending the work of Kapralov and Krachun to \textsf{Max
$k$-LIN}-$\bmod\; q$ to $k>2$ and $q>2$ (while getting optimal hardness
results) is the main technical contribution of this work. Each one of these
extensions provides non-trivial technical challenges that we overcome in this
work.
