Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR22-066 | 4th May 2022 23:44

#### On sketching approximations for symmetric Boolean CSPs

TR22-066
Authors: Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy
Publication: 5th May 2022 00:01
Keywords:

Abstract:

A Boolean maximum constraint satisfaction problem, Max-CSP$$(f)$$, is specified by a predicate $$f:\{-1,1\}^k\to\{0,1\}$$. An $$n$$-variable instance of Max-CSP$$(f)$$ consists of a list of constraints, each of which applies $$f$$ to $$k$$ distinct literals drawn from the $$n$$ variables. For $$k=2$$, Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios characterizing the $$\sqrt n$$-space streaming approximability of every predicate. For $$k \geq 3$$, Chou, Golovnev, Sudan, and Velusamy [CGSV21, arXiv:2102.12351] proved a general dichotomy theorem for $$\sqrt n$$-space sketching algorithms: For every $$f$$, there exists $$\alpha(f)\in (0,1]$$ such that for every $$\epsilon>0$$, Max-CSP$$(f)$$ is $$(\alpha(f)-\epsilon)$$-approximable by an $$O(\log n)$$-space linear sketching algorithm, but $$(\alpha(f)+\epsilon)$$-approximation sketching algorithms require $$\Omega(\sqrt{n})$$ space.

In this work, we give closed-form expressions for the sketching approximation ratios of multiple families of symmetric Boolean functions. Letting $$\alpha'_k = 2^{-(k-1)} (1-k^{-2})^{(k-1)/2}$$, we show that for odd $$k \geq 3$$, $$\alpha(k$$AND$$)\, = \alpha'_k$$, and for even $$k \geq 2$$, $$\alpha(k$$AND$$)\, = 2\alpha'_{k+1}$$. Thus, for every $$k$$, $$k$$AND can be $$(2-o(1))2^{-k}$$-approximated by $$O(\log n)$$-space sketching algorithms; we contrast this with a lower bound of Chou, Golovnev, Sudan, Velingker, and Velusamy [STOC 2022] implying that streaming $$(2+\epsilon)\cdot2^{-k}$$-approximations require $$\Omega(n)$$ space! We also resolve the ratio for the "at-least-$$(k-1)$$-$$1$$'s" function for all even $$k$$; the "exactly-$$\frac{k+1}2$$-$$1$$'s" function for odd $$k \in \{3,\ldots,51\}$$; and fifteen other functions. We stress here that for general $$f$$, the dichotomy theorem in [CGSV21] only implies that $$\alpha(f)$$ can be computed to arbitrary precision in $$\textbf{PSPACE}$$, and thus closed-form expressions need not have existed a priori. Our analyses involve identifying and exploiting structural "saddle-point" properties of this dichotomy.

Separately, for all threshold functions, we give optimal "bias-based" approximation algorithms generalizing [CGV20] while simplifying [CGSV21]. Finally, we investigate the $$\sqrt n$$-space streaming lower bounds in [CGSV21], and show that they are incomplete for $$3$$AND, i.e., they fail to rule out $$(\alpha(3$$AND$$)-\epsilon)$$-approximations in $$o(\sqrt n)$$ space.

ISSN 1433-8092 | Imprint