BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T075917Z
UID:Seminar-EcCo-606@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20190619T130000
DTEND:20190619T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Argyrios Deligkas: Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem\n\nWe study the problem of finding an exact solution to the consensus halving problem. While recent work has shown that the approximate version of this problem is PPA-complete, we show that the exact version is much harder. Specifically, finding a solution with n agents and n cuts is FIXP-hard, and deciding whether there exists a solution with fewer than n cuts is ETR-complete. We also give a QPTAS for the case where each agent's valuation is a polynomial. \nAlong the way, we define a new complexity class BU, which captures all problems that can be reduced to solving an instance of the Borsuk-Ulam problem exactly. We show that FIXP ? BU ? TFETR and that LinearBU = PPA, where LinearBU is the subclass of BU in which the Borsuk-Ulam instance is specified by a linear arithmetic circuit.\n\nJoint work with John Fearnley, Themistoklis Melissourgos and Paul Spirakis.\nTo appear in ICALP '19.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=606
LOCATION:
END:VEVENT
END:VCALENDAR