We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In~particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first variable (the president) and the sum of the votes of all remaining variables. The pure version of this function is when the president can only be overruled by when all remaining variables agree. For every $k \geq 5$, we show that CSPs where the underlying predicate is a pure monarchy function on $k$ variables have no non-trivial sketching approximation algorithm in $o(\sqrt{n})$ space. We also show infinitely many weaker monarchy functions for which CSPs using such constraints are non-trivially approximable by $O(\log(n))$ space sketching algorithms. Moreover, we give the first example of sketching approximable asymmetric Boolean CSPs. Our results work within the framework of Chou, Golovnev, Sudan, and Velusamy (FOCS 2021) that characterizes the sketching approximability of all CSPs. Their framework can be applied naturally to get a computer-aided analysis of the approximability of any specific constraint satisfaction problem. The novelty of our work is in using their work to get an analysis that applies to infinitely many problems simultaneously.
翻译:我们分析布林域限制满意度问题的草图, 布林域的限制是平衡的线性阈值功能。 在外表中, 我们探索君主式功能的相似性, 该功能的价值是由第一个变量( 总统) 的票数和所有剩余变量的票数之和的加权组合决定的。 这个功能的纯版是当总统只能在所有剩余变量都同意时才能被推翻的时候。 对于每5美元, 我们显示, 在每5美元变量中, 基本上游功能是纯正君主制函数, 用于美元变量的纯正线性线性阈值。 在 美元空间中, 我们探索君主制类似功能的近似功能的近似可度算法的近似性。 我们还展示了无限许多较弱的君主制功能, 而使用这种限制的CSP的票数是非奇异的。 此外, 我们的第CLO( log (n) (n) ) 空间草图算算法的首个示例是, 我们的CLovovelevevevev 和 CSP 的逻辑框架中, 我们的工作结果应用了Calbilable- calbilable 分析。