Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914566167855104 |
|---|---|
| author | Bedert, Benjamin Nakajima, Tamio-Vesa Okrasa, Karolina Živný, Stanislav |
| author_facet | Bedert, Benjamin Nakajima, Tamio-Vesa Okrasa, Karolina Živný, Stanislav |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_17878 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa Bedert, Benjamin Nakajima, Tamio-Vesa Okrasa, Karolina Živný, Stanislav Data Structures and Algorithms Computational Complexity Discrete Mathematics Combinatorics 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. |
| title | Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa |
| topic | Data Structures and Algorithms Computational Complexity Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2507.17878 |