{"ID":2891499,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.17878","arxiv_id":"2507.17878","title":"Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa","abstract":"We introduce a new notion of sparsification, called \\emph{strong sparsification}, in which constraints are not removed but variables can be merged. As our main result, we present a strong sparsification algorithm for 1-in-3-SAT. The correctness of the algorithm relies on establishing a sub-quadratic bound on the size of certain sets of vectors in $\\mathbb{F}_2^d$. This result, obtained using the recent \\emph{Polynomial Freiman-Ruzsa Theorem} (Gowers, Green, Manners and Tao, Ann. Math. 2025), could be of independent interest. As an application, we improve the state-of-the-art algorithm for approximating linearly-ordered colourings of 3-uniform hypergraphs (Håstad, Martinsson, Nakajima and{Ž}ivn{ý}, APPROX 2024). We also investigate the existence of strong sparsification algorithms for other constraint satisfaction problems.","short_abstract":"We introduce a new notion of sparsification, called \\emph{strong sparsification}, in which constraints are not removed but variables can be merged. As our main result, we present a strong sparsification algorithm for 1-in-3-SAT. The correctness of the algorithm relies on establishing a sub-quadratic bound on the size o...","url_abs":"https://arxiv.org/abs/2507.17878","url_pdf":"https://arxiv.org/pdf/2507.17878v4","authors":"[\"Benjamin Bedert\",\"Tamio-Vesa Nakajima\",\"Karolina Okrasa\",\"Stanislav Živný\"]","published":"2025-07-23T19:11:32Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\",\"cs.DM\",\"math.CO\"]","methods":"[]","has_code":false}