BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260913T144739Z
UID:Seminar-EcCo-616@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20200219T130000
DTEND:20200219T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Alexandros Hollender: A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting\n\nThe classes PPA-k have attracted attention lately because they are the prime candidates for capturing the complexity of Necklace Splitting with k thieves. However, these classes are not known to have complete problems of a topological nature, which impedes any progress towards settling the complexity of the problem. On the contrary, such problems have been pivotal in obtaining completeness results for PPAD and PPA, for several important problems, such as finding a Nash equilibrium and Necklace Splitting with two thieves.\n \nIn this paper, we provide the first topological characterization of the classes PPA-p, where p is a prime. First, we show that the computational problem associated with a simple generalization of Tucker's Lemma, termed p-Polygon Tucker, as well the associated Borsuk-Ulam-type theorem, p-Polygon Borsuk Ulam, are PPA-p-complete. Then, we show that the computational version of the well-known BSS Theorem, as well as the associated BSS-Tucker problem are PPA-p-complete, which answers an open question of Goos et al (2019). Finally, using a different generalization of Tucker's Lemma (termed Z_p-Star-Tucker), which we prove to be PPA-p-complete, we prove that k-thieves Necklace Splitting is in PPA-k, for any k which is a prime power. The latter result partially answers another open problem raised by Goos et al (2019) and Filos-Ratsikas and Goldberg (2019).\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=616
LOCATION:
END:VEVENT
END:VCALENDAR