Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
For researchers in constraint satisfaction and hypergraph colouring, this work provides a new sparsification technique and an improved approximation algorithm.
The authors introduce strong sparsification, a technique that merges variables instead of removing constraints, and present an algorithm for 1-in-3-SAT. Using the Polynomial Freiman-Ruzsa Theorem, they improve the state-of-the-art algorithm for approximating linearly-ordered colourings of 3-uniform hypergraphs.
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.