2021/05/03 by Chi-Ning Chou, Chou, Chi-Ning, Alexander Golovnev +5 · 5 citations
Computer Science · Engineering · #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Machine Learning and Algorithms #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2105.01161
openalex publication_date 2021/05/03 · openalex created_date 2023/03/20 · openalex updated_date 2026/07/28
A constraint satisfaction problem (CSP), \textsfMax-CSP(F), is specified by a finite set of constraints F ⊆ \[q]k → \0,1\\ for positive integers q and k. An instance of the problem on n variables is given by m applications of constraints from F to subsequences of the n variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the (γ,β)-approximation version of the problem for parameters 0 ≤ β< γ≤ 1, the goal is to distinguish instances where at least γ fraction of the constraints can be satisfied from instances where at most β fraction of the constraints can be satisfied. In this work we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family F and every β< γ, we show that either a linear sketching algorithm solves the problem in polylogarithmic space, or the problem is not solvable by any sketching algorithm in o(√(n)) space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of q=k=2, where we get a dichotomy, and the case when the satisfying assignments of the constraints of F support a distribution on [q]k with uniform marginals. Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variables q=2, binary constraints k=2, singleton families |F|=1 and only considered the setting where constraints are placed on literals rather than variables.