Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa

Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa +1

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…