Linear space streaming lower bounds for approximating CSPs
Linear space streaming lower bounds for approximating CSPs
复制标题
用于近似 CSP 的线性空间流下界
DOI：
10.1145/3519935.3519983
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Velusamy, Santhoshini
中科院分区：
文献类型：
--
作者：
Chou, Chi-Ning;Golovnev, Alexander;Sudan, Madhu;Velingker, Ameya;Velusamy, Santhoshini
我们考虑流媒体环境中约束满足问题的可逼近性。对于n个变量取值于{0，.，q −1}的约束满足问题（CSP），我们证明了即使在O（n）约束的情况下，在平凡逼近性上提高一个因子q也需要Ω（n）空间.我们还确定了一个广泛的子类的问题，任何改进的平凡逼近需要Ω（n）空间。关键技术核心是Maxk-LIN-modq问题的最优q−（k−1）-不可逼近性，Maxk-LIN-modq问题是Max CSP问题，其中每个约束都由k −1个线性方程组modqoverk变量给出。我们的工作建立在Kapralov和Krachun（Proc. STOC 2019）的突破性工作的基础上，并扩展了Kapralov和Krachun（Proc. STOC 2019）的突破性工作，他们展示了图中MaxCut问题的任何非平凡近似的线性下限。MaxCut大致对应于Maxk-LIN-modq的情况，其中k =q=2。对于流设置中的一般CSP，先前的结果仅产生Ω（n）空间边界。特别是没有线性空间下限是已知的近似因子小于1/2 foranyCSP。将Kapralov和Krachun的工作扩展到Maxk-LIN-modqtok>2和q>2（同时获得最佳硬度结果）是这项工作的主要技术贡献。这些扩展中的每一个都提供了我们在这项工作中克服的重要技术挑战。
We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) onnvariables taking values in {0,…,q−1}, we prove that improving over the trivial approximability by a factor ofqrequires Ω(n) space even on instances withO(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 Maxk-LIN-modqproblem, which is the Max CSP problem where every constraint is given by a system ofk−1 linear equations modqoverkvariables.Our work builds on and extends the breakthrough work of Kapralov and Krachun (Proc. STOC 2019) who showed a linear lower bound on any non-trivial approximation of the MaxCut problem in graphs. MaxCut corresponds roughly to the case of Maxk-LIN-modqwithk=q=2. For general CSPs in the streaming setting, prior results only yielded Ω(√n) space bounds. In particular no linear space lower bound was known for an approximation factor less than 1/2 foranyCSP. Extending the work of Kapralov and Krachun to Maxk-LIN-modqtok>2 andq>2 (while getting optimal hardness results) is the main technical contribution of this work. Each one of these extensions provides non-trivial technical challenges that we overcome in this work.
登录
查看更多内容
集合覆盖问题的单遍流复杂性的严格界限
DOI：
--
发表时间：
2016
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Sepehr Assadi;S. Khanna;Yang Li
通讯作者：
Yang Li
每个排序CSP的流近似电阻
DOI：
10.4230/lipics.approx/random.2021.17
发表时间：
2021
期刊：
Comput. Complex.
影响因子：
--
作者：
Noah G. Singer;M. Sudan;Santhoshini Velusamy
通讯作者：
Santhoshini Velusamy
独特游戏的流媒体硬度
DOI：
10.4230/lipics.approx-random.2019.5
发表时间：
2018
期刊：
ArXiv
影响因子：
--
作者：
V. Guruswami;Runzhou Tao
通讯作者：
Runzhou Tao
近似最大 2CSP 和最大非循环子图的流复杂度
DOI：
10.4230/lipics.approx-random.2017.8
发表时间：
2017
期刊：
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
V. Guruswami;A. Velingker;Santhoshini Velusamy
通讯作者：
Santhoshini Velusamy
循环计数、MAX-CUT、匹配大小和其他问题的多通道图流下限
DOI：
--
发表时间：
2020
期刊：
Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Assadi, Sepehr;Kol, Gillat;Saxena, Raghuvansh;Yu, Huacheng
通讯作者：
Yu, Huacheng