BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260530T131110Z
UID:Seminar-ACTO-497@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20191023T140000
DTEND:20191023T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Aris Filos-Ratsikas: Necklace Splitting and Natural PPA-Complete Problems\n\nThe class TFNP was defined by Meggido and Papadimitriou in 1991 and contains total search problems, i.e., problems for which a solution always exists and is verifiable in polynomial time. Among its many subclasses, defined by Papadimitriou in 1994 (as well as in subsequent works), PPAD has been largely successful in capturing the computational complexity of many interesting problems, with the most prominent example being the PPAD-completeness of computing a Nash equilibrium. On the other hand, the class PPA was not known to have any natural complete problems. In this talk, I will go present some recent work (with Paul Goldberg), in which we identify the first natural PPA-complete problems. It turns out that one of them is the well-known Necklace Splitting problem (Alon 1987) from mathematics, the complexity of which was posed as an open question several times over the years.\n\nThe talk will not be very technical and will also serve as a brief introduction to the subclasses of TFNP for a wider audience.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=497
LOCATION:
END:VEVENT
END:VCALENDAR