BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Aris Filos-Ratsikas (University of Liverpool)
DTSTART:20201027T163000Z
DTEND:20201027T170000Z
DTSTAMP:20260417T204922Z
UID:LA-CoCo/7
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/LA-CoCo/7/">
 The Complexity of Necklace Splitting\, Consensus-Halving and Discrete Ham 
 Sandwich</a>\nby Aris Filos-Ratsikas (University of Liverpool) as part of 
 LA Combinatorics and Complexity Seminar\n\n\nAbstract\nThe <i>Necklace Spl
 itting problem</i> and its continuous counterpart\, the <i>Consensus-Halvi
 ng problem</i>\, as well as the <i>Discrete Ham Sandwich problem</i>\, are
  classical problems in combinatorics\, with applications to fair division 
 and social choice theory.  A distinctive characteristic of these problems 
 is that they always have a solution\, but it was not known until recently 
 whether such a solution can be found efficiently. We study the computation
 al complexity of these problems and show that they are complete for the co
 mputational class <b>PPA</b>. A direct implication of this result is that 
 the problems are unlikely to be solvable in polynomial time.\n\nP.S. For p
 apers\, see https://arxiv.org/abs/1711.04503 and https://arxiv.org/abs/180
 5.12559\n
LOCATION:https://researchseminars.org/talk/LA-CoCo/7/
END:VEVENT
END:VCALENDAR