Journal article icon

Journal article

The classes PPA-k: Existence from arguments modulo k

Abstract:

The complexity classes PPA-k, k≥2, have recently emerged as the main candidates for capturing the complexity of important problems in fair division, in particular Alon's NECKLACE-SPLITTING problem with k thieves. Indeed, the problem with two thieves has been shown complete for PPA = PPA-2. In this work, we present structural results which provide a solid foundation for the further study of these classes. Namely, we investigate the classes PPA-k in terms of (i) equivalent definitions, (...

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

Actions


Access Document


Files:
Publisher copy:
10.1016/j.tcs.2021.06.016

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
All Souls College
Role:
Author
ORCID:
0000-0001-5255-9349
Publisher:
Elsevier Publisher's website
Journal:
Theoretical Computer Science Journal website
Volume:
885
Pages:
15-29
Publication date:
2021-06-17
Acceptance date:
2021-06-13
DOI:
EISSN:
1879-2294
ISSN:
0304-3975
Language:
English
Keywords:
Pubs id:
1217982
Local pid:
pubs:1217982
Deposit date:
2022-03-21

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