Tuesday, October 27, 2020 at 9:30am to 10:00am
Aris Filos-Ratsikas, University of Liverpool, UK
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
Zoom Meeting: https://ucla.zoom.us/j/96564290758
Meeting ID: 965 6429 0758
Passcode: Please see your email for the passcode to join via Zoom
Warning: You must be registered under your name to be admitted.