BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T205220Z
UID:Seminar-dept-1298@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20251104T130000
DTEND:20251104T140000
SUMMARY:School Seminar Series
DESCRIPTION:Karolina Okrasa: Strong sparsification for 1-in-3-Sat\n\n 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.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1298
LOCATION:ELEC201, 2th Floor Lecture Theater EEE
END:VEVENT
END:VCALENDAR