A Dichotomy Theorem for Multi-pass Streaming CSPs

In a constraint satisfaction problem (CSP) in the single-pass streaming model, an algorithm is given the constraints C1,…,Cm of an instance one after another (in some fixed order), and its goal is to approximate the value of the instance, i.e., the maximum fraction of constraints that can be satisfied simultaneously. In the p-pass streaming model the algorithm is given p passes over the input stream (in the same order), after which it is required to output an approximation of the value of the instance. We show a dichotomy result for p-pass streaming algorithms for all CSPs and for up to polynomially many passes. More precisely, we prove that for any arity parameter k, finite alphabet Σ, collection F of k-ary predicates over Σ and any c∈ (0,1), there exists 0<s≤ c such that: