期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on n variables taking values in 0q−1 , we prove that improving over the trivial approximability by a factor of q requires (n) space even on instances with O(n) constraints. We also identify a broad subclass of problems for which any improvement over the trivial approximability requires (n) space. The key technical core is an optimal, q−(k−1)-inapproximability for the case where every constraint is given by a system of k−1 linear equations modq over k variables. Prior to our work, no such hardness was known for an approximation factor less than 12 for any CSP. Our work builds on and extends the work of Kapralov and Krachun (Proc. STOC 2019) who showed a linear lower bound on any non-trivial approximation of the max cut in graphs. This corresponds roughly to the case of Max k-LIN-modq with k=q=2. Each one of the extensions provides non-trivial technical challenges that we overcome in this work.
