BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260411T111345Z
UID:Seminar-EcCo-1003@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20210630T130000
DTEND:20210630T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Argyrios Deligkas: Square-Cut Pizza Sharing is PPA-complete\n\nWe study the computational complexity of computing solutions for the square-cut pizza sharing problem. In this problem, we have n mass distributions in the plane, and the task is to find a path that uses horizontal and vertical segments that splits each of the masses in half while making at most n−1 turns. We show that finding an approximate solution to this problem is PPA-complete, while finding an exact solution is FIXP-hard and in BU. Our PPA-hardness result applies even when all mass distributions are unions of non-overlapping squares, and our FIXP-hardness result applies even when all mass distributions are unions of weighted squares and right-angled triangles. When the path is restricted to have at most n−2 turns, we show that the approximate problem becomes NP-complete, and the exact problem becomes ETR-complete.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1003
LOCATION:
END:VEVENT
END:VCALENDAR