Cores Characterize the One-Pass Streaming Complexity of CSPs

Joshua Brakensiek, Aaron Putterman, Amatya Sharma +1

We study the one-pass streaming complexity of CSPs over a fixed finite relation $R$ under three natural objectives: $\text{SAT}(R)$, deciding whether all constraints can be satis…