2021/02/24 by Chi-Ning Chou, Chou, Chi-Ning, Alexander Golovnev +5 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2102.12351
openalex publication_date 2021/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work we consider the approximability of \textsfMax-CSP(f) in the context of sketching algorithms and completely characterize the approximability of all Boolean CSPs. Specifically, given f, γ and β we show that either (1) the (γ,β)-approximation version of \textsfMax-CSP(f) has a linear sketching algorithm using O(log n) space, or (2) for every ε> 0 the (γ-ε,β+ε)-approximation version of \textsfMax-CSP(f) requires Ω(√(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.