Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat
We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an explicit constant α, s.t. for any (i) there is an ( α-ε)-streaming approximation using space O(logn); and (ii) any ( α+ε)-streaming …