{"ID":2867793,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.17926","arxiv_id":"2509.17926","title":"Sketching approximations and LP approximations for finite CSPs are related","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 $Ω(\\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.","short_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 $Ω(\\sqrt{n})$-space sketching lower bound. We also show that all existing linear space streami...","url_abs":"https://arxiv.org/abs/2509.17926","url_pdf":"https://arxiv.org/pdf/2509.17926v1","authors":"[\"Noah G. Singer\",\"Madhur Tulsiani\",\"Santhoshini Velusamy\"]","published":"2025-09-22T15:51:33Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}