On the Complexity of Consensus-Halving and Necklace Splitting
This event is free and open to the publicAdd to Google Calendar
(Joint with Purdue)
The Necklace Splitting problem and its continuous counterpart, the Consensus-Halving problem, are classical problems in combinatorics, with applications to fair division and social choice theory. A distinctive characteristic of these problems is that they are total, i.e., they always have a solution, but it was not known until recently whether such a solution can be found efficiently. In this talk, I will present results from a series of recent papers (from 2018 to 2021) related to the computational complexity of these problems. The talk will also provide a gentle introduction to the computational subclasses of the class TFNP, the class of total search problems for which a solution can be verified in polynomial time.