Aris Filos-Ratsikas, University of Liverpool, UK

Abstract:
The Necklace Splitting problem and its continuous counterpart, the Consensus-Halving problem, as well as the Discrete Ham Sandwich problem, 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 computational complexity of these problems and show that they are complete for the computational class PPA. A direct implication of this result is that the problems are unlikely to be solvable in polynomial time.

P.S. For papers, see arxiv.org/abs/1711.04503 and arxiv.org/abs/1805.12559