Title: Sketching approximations and LP approximations for finite CSPs are related Show Chinese title

Title: 有限CSP的草图近似和LP近似是相关的

Abstract: We identify a connection between the approximability of CSPs in two models: (i) sublinear space streaming algorithms, and (ii) the basic LP relaxation. We show that whenever the basic LP admits an integrality gap, there is an $\Omega(\sqrt{n})$-space sketching lower bound. We also show that all existing linear space streaming lower bounds for Max-CSPs can be lifted to integrality gap instances for basic LPs. For bounded-degree graphs, by combining the distributed algorithm of Yoshida (STOC 2011) for approximately solving the basic LP with techniques described in Saxena, Singer, Sudan, and Velusamy (SODA 2025) for simulating a distributed algorithm by a sublinear space streaming algorithm on bounded-degree instances of Max-DICUT, it appears that there are sublinear space streaming algorithms implementing the basic LP, for every CSP. Based on our results, we conjecture the following dichotomy theorem: Whenever the basic LP admits an integrality gap, there is a linear space single-pass streaming lower bound, and when the LP is roundable, there is a sublinear space streaming algorithm. Show Chinese abstract

Abstract: 我们发现两个模型中CSP近似性的联系： (i) 子线性空间流算法，和 (ii) 基本LP松弛。 我们证明，每当基本LP存在整数间隙时，就存在$\Omega(\sqrt{n})$-空间的sketching下界。 我们还证明，所有现有的Max-CSPs线性空间流下界都可以提升为基本LP的整数间隙实例。 对于有界度图，通过结合Yoshida（STOC 2011）用于近似求解基本LP的分布式算法，以及Saxena、Singer、Sudan和Velusamy（SODA 2025）描述的在有界度Max-DICUT实例上通过子线性空间流算法模拟分布式算法的技术，似乎对于每个CSP都存在实现基本LP的子线性空间流算法。 基于我们的结果，我们提出以下二分定理猜想：每当基本LP存在整数间隙时，就存在线性空间单次遍历流下界，而当LP可圆整时，就存在子线性空间流算法。