Sparsification of 1-in-3-SAT
Tuesday, September 16, 2025 - 4:15pm to 5:15pm
Refreshments:
4:00 PM
Location:
32-G449 (Kiva/Patil)
Speaker:
Standa Živný, Oxford
Biography:
https://www.cs.ox.ac.uk/standa.zivny/
Seminar group:
I will introduce a new notion of sparsification that doesn't drop constraints but merges variables. Using tools from additive combinatorics, I will then show that 1-in-3-SAT admits a sub-quadratic sparsifier. As an application, I will present an improved approximation algorithm for finding a linearly-ordered colouring of 3-uniform hypergraphs. Based on joint work with B. Bedert, T.-V. Nakajima, and K. Okrasa, to appear in FOCS'25.