On the Complexity of Consensus-Halving and Necklace Splitting

(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.