  An ordering constraint satisfaction problem (OCSP) is defined by a family
$\mathcal{F}$ of predicates mapping permutations on $\{1,\ldots,k\}$ to
$\{0,1\}$. An instance of Max-OCSP($\mathcal{F}$) on $n$ variables consists of
a list of constraints, each consisting of a predicate from $\mathcal{F}$
applied on $k$ distinct variables. The goal is to find an ordering of the $n$
variables that maximizes the number of constraints for which the induced
ordering on the $k$ variables satisfies the predicate. OCSPs capture
well-studied problems including `maximum acyclic subgraph' (MAS) and "maximum
betweenness".
  In this work, we consider the task of approximating the maximum number of
satisfiable constraints in the (single-pass) streaming setting, when an
instance is presented as a stream of constraints. We show that for every
$\mathcal{F}$, Max-OCSP($\mathcal{F}$) is approximation-resistant to
$o(n)$-space streaming algorithms, i.e., algorithms using $o(n)$ space cannot
distinguish streams where almost every constraint is satisfiable from streams
where no ordering beats the random ordering by a noticeable amount. This space
bound is tight up to polylogarithmic factors. In the case of MAS our result
shows that for every $\epsilon>0$, MAS is not $(1/2+\epsilon)$-approximable in
$o(n)$ space. The previous best inapproximability result, due to Guruswami and
Tao (APPROX'19), only ruled out $3/4$-approximations in $o(\sqrt n)$ space.
  Our results build on a recent work of Chou, Golovnev, Sudan, Velingker, and
Velusamy (STOC'22), who provide a tight, linear-space inapproximability theorem
for a broad class of "standard" (i.e., non-ordering) constraint satisfaction
problems (CSPs) over arbitrary (finite) alphabets. We construct a family of
appropriate standard CSPs from any given OCSP, apply their hardness result to
this family of CSPs, and then convert back to our OCSP.
