L'article "Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa" présente un nouveau concept de sparsification appelé sparsification forte, où les variables peuvent être fusionnées au lieu de supprimer des contraintes. Les auteurs présentent un algorithme de sparsification forte pour le problème 1-in-3-SAT, qui améliore les bornes supérieures quadratiques précédentes.
Le résultat technique clé de l'article est une borne sous-quadratique sur la taille de certains ensembles de vecteurs dans F_d^2, obtenue en utilisant le Théorème Polynômique Freiman-Ruzsa. Ce résultat pourrait avoir un intérêt indépendant.
Les auteurs appliquent également leur algorithme de sparsification forte pour améliorer l'algorithme de pointe pour approximer les colorations linéairement ordonnées des hypergraphes 3-uniformes.
Principales contributions :
* Introduire le concept de sparsification forte.
* Présenter un algorithme de sparsification forte pour 1-in-3-SAT avec une performance sous-quadratique.
* Obtenir une borne sous-quadratique sur la taille de certains ensembles de vecteurs dans F_d^2 en utilisant le Théorème Polynômique Freiman-Ruzsa.
* Appliquer l'algorithme de sparsification forte pour améliorer l'algorithme de pointe pour approximer les colorations linéairement ordonnées des hypergraphes 3-uniformes.