Los Angeles Combinatorics and Complexity Seminar: The Complexity of Necklace Splitting, Consensus-Halving and Discrete Ham Sandwich

Tuesday, October 27, 2020 at 9:30am to 10:00am

This is a past event.
Virtual Event


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

Dial-In Information

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.

Event Type

Lecture / Talk / Workshop

Department
Mathematics
Add this to your calendar

Recent Activity