Boyland, Joanna ;
Hwang, Michael ;
Prasad, Tarun ;
Singer, Noah ;
Velusamy, Santhoshini
On Sketching Approximations for Symmetric Boolean CSPs
Abstract
A Boolean maximum constraint satisfaction problem, MaxCSP(f), is specified by a predicate f:{1,1}^k → {0,1}. An nvariable instance of MaxCSP(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 [Chou et al., 2020] obtained explicit ratios characterizing the √ nspace streaming approximability of every predicate. For k ≥ 3, Chou, Golovnev, Sudan, and Velusamy [Chou et al., 2022] proved a general dichotomy theorem for √ nspace sketching algorithms: For every f, there exists α(f) ∈ (0,1] such that for every ε > 0, MaxCSP(f) is (α(f)ε)approximable by an O(log n)space linear sketching algorithm, but (α(f)+ε)approximation sketching algorithms require Ω(√n) space.
In this work, we give closedform expressions for the sketching approximation ratios of multiple families of symmetric Boolean functions. Letting α'_k = 2^{(k1)} (1k^{2})^{(k1)/2}, we show that for odd k ≥ 3, α(kAND) = α'_k, and for even k ≥ 2, α(kAND) = 2α'_{k+1}. Thus, for every k, kAND can be (2o(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 [Chou et al., 2022] implying that streaming (2+ε)2^{k}approximations require Ω(n) space! We also resolve the ratio for the "atleast(k1)1’s" function for all even k; the "exactly(k+1)/21’s" function for odd k ∈ {3,…,51}; and fifteen other functions. We stress here that for general f, the dichotomy theorem in [Chou et al., 2022] only implies that α(f) can be computed to arbitrary precision in PSPACE, and thus closedform expressions need not have existed a priori. Our analyses involve identifying and exploiting structural "saddlepoint" properties of this dichotomy.
Separately, for all threshold functions, we give optimal "biasbased" approximation algorithms generalizing [Chou et al., 2020] while simplifying [Chou et al., 2022]. Finally, we investigate the √ nspace streaming lower bounds in [Chou et al., 2022], and show that they are incomplete for 3AND, i.e., they fail to rule out (α(3AND})ε)approximations in o(√ n) space.
BibTeX  Entry
@InProceedings{boyland_et_al:LIPIcs.APPROX/RANDOM.2022.38,
author = {Boyland, Joanna and Hwang, Michael and Prasad, Tarun and Singer, Noah and Velusamy, Santhoshini},
title = {{On Sketching Approximations for Symmetric Boolean CSPs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {38:138:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17160},
URN = {urn:nbn:de:0030drops171604},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.38},
annote = {Keywords: Streaming algorithms, constraint satisfaction problems, approximability}
}
15.09.2022
Keywords: 

Streaming algorithms, constraint satisfaction problems, approximability 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Issue date: 

2022 
Date of publication: 

15.09.2022 
Supplementary Material: 

InteractiveResource (Interactive Mathematica notebook): https://notebookarchive.org/202203a5vpzhg/ 