Conference item icon

Conference item

The complexity of splitting necklaces and bisecting ham sandwiches

Abstract:

We resolve the computational complexity of two problems known as Necklace-splitting and Discrete Ham Sandwich showing that they are PPA-complete. For Necklace-splitting, this result is specific to the important special case in which two thieves share the necklace. We do this via a PPA-completeness result for an approximate version of the Consensus-halving problem, strengthening our recent result that the problem is PPA-complete for inverse-exponential precision. At the heart of our constructi...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1145/3313276.3316334

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
ORCID:
0000-0002-5436-7890
Publisher:
Association for Computing Machinery
Journal:
STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing More from this journal
Pages:
638-649
Publication date:
2019-06-23
Event title:
51st Annual ACM SIGACT Symposium
Event location:
Phoenix, Arizona, USA
Event website:
https://dl.acm.org/doi/proceedings/10.1145/3313276
Event start date:
2019-06-23
Event end date:
2019-06-26
DOI:
ISSN:
0737-8017
ISBN:
9781450367059
Language:
English
Keywords:
Pubs id:
860079
Local pid:
pubs:860079
Deposit date:
2020-01-29

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP