Revisiting maximum satisfiability and related problems in data streams

We revisit the maximum satisfiability problem (Max-SAT) in the data stream model. In this problem, the stream consists of m clauses that are disjunctions of literals drawn from n Boolean variables. The objective is to find an assignment to the variables that maximizes the number root of satisfied clauses. Chou et al. (FOCS 2020) showed that omega( n) space is necessary to yield a root root 2/2 +e approximation of the optimum value; they also presented an algorithm that yields a 2/2 - e approximation of the optimum value using O(e-2 log n) space. In this paper, we not only focus on approximating the optimum value, but also on obtaining the corresponding Boolean assignment using sublinear o(mn) space. We present randomized single-pass algorithms that w.h.p.1 yield:center dot A 1 - e approximation using Õ(n/e3) space and exponential post-processing time center dot A 3/4 - e approximation using Õ(n/e) space and polynomial post-processing time.Our ideas also extend to dynamic streams. However, we show that the streaming k-SAT problem, which asks whether one can satisfy all size -k input clauses, must use omega(nk) space. We also consider the related minimum satisfiability problem (Min-SAT), introduced by Kohli et al. (SIAM J. Discrete Math. 1994), that asks to find an assignment that minimizes the number of satisfied clauses. For this problem, we give a Õ(n2/e2) space algorithm, which is sublinear when m = co(n), that yields an a +e approximation where a is the approximation guarantee of the offline root algorithm. If each variable appears in at most f clauses, we show that a 2 fn approximation using Õ(n) space is possible. Finally, for the Max-AND-SAT problem where clauses are conjunctions of literals, we show that any single-pass algorithm that approximates the optimal value up to a factor better than 1/2 with success probability at least 2/3 must use omega(mn) space.

Automated summary

This paper addresses the maximum satisfiability problem in the data stream model. It presents algorithms that achieve approximations to the optimum value and corresponding Boolean assignments in sublinear space complexity. The paper also discusses related problems and provides approximation algorithms and space complexity for them.