Approximability of all Boolean CSPs with linear sketches

Abstract

In this work we consider the approximability of $\text{Max-CSP}(f)$ in the context of sketching algorithms and completely characterize the approximability of all Boolean CSPs. Specifically, given $f$, $\gamma$ and $\beta$ we show that either (1) the $(\gamma ,\beta )$-approximation version of $\text{Max-CSP}(f)$ has a linear sketching algorithm using $O(\log n)$ space, or (2) for every $\epsilon >0$ the $(\gamma -\epsilon ,\beta +\epsilon )$-approximation version of $\text{Max-CSP}(f)$ requires $\Omega (\sqrt{n})$ space for any sketching algorithm. We also prove lower bounds against streaming algorithms for several CSPs. In particular, we recover the streaming dichotomy of [CGV20] for $k=2$ and show streaming approximation resistance of all CSPs for which $f^{-1}(1)$ supports a distribution with uniform marginals. Our positive results show wider applicability of bias-based algorithms used previously by [GVV17] and [CGV20] by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [KKS15], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results.

Cited by in corpus (1)

• Streaming complexity of CSPs with randomly ordered constraints