Strong sparsification for 1-in-3-Sat

Karolina Okrasa ( University of Oxford )

We introduce a notion of sparsification, called strong sparsification, in which constraints are not removed but variables can be merged. Building on recent advances in the area of additive combinatorics, we prove that the instances of 1-in-3-Sat can be strongly sparsified so that the number of clauses becomes subquadratic. As an application, we improve the state-of-the-art algorithm for approximating linearly-ordered colourings of 3-uniform hypergraph, one of the generalizations of the classic notion of graph colouring.

This is a joint work with Benjamin Bedert, Tamio-Vesa Nakajima, and Standa Živný.