Strong sparsification for 1-in-3-Sat

4^th November 2025, 13:00 ELEC201, 2th Floor Lecture Theater EEE
Karolina Okrasa
University of Oxford

Abstract

We introduce a new notion of sparsification, called strong sparsification, in which constraints are not removed but variables can be merged. Using the prominent results from the area of additive combinatorics, we show 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.