Consensus Halving is PPA-Complete

Aris Filos-Ratsikas; Paul W. Goldberg

doi:10.1145/3188745.3188880

Consensus Halving is PPA-Complete

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We show that the computational problem Consensus Halving is PPA-Complete, the first PPA-Completeness result for a problem whose definition does not involve an explicit circuit. We also show that an approximate version of this problem is polynomial-time equivalent to Necklace Splitting, which establishes PPAD-hardness for Necklace Splitting and suggests that it is also PPA-Complete.

Original language	English
Title of host publication	Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
Editors	Ilias Diakonikolas, David Kempe, Monika Henzinger
Place of Publication	New York, NY, USA
Publisher	Association for Computing Machinery, Inc
Pages	51–64
ISBN (Electronic)	9781450355599
DOIs	https://doi.org/10.1145/3188745.3188880
Publication status	Published - 20 Jun 2018
Event	50th Annual ACM Symposium on the Theory of Computing - Los Angeles, United States Duration: 25 Jun 2018 → 29 Jun 2018 http://acm-stoc.org/stoc2018/

Publication series

Name	STOC 2018
Publisher	Association for Computing Machinery

Conference

Conference	50th Annual ACM Symposium on the Theory of Computing
Abbreviated title	STOC 2018
Country/Territory	United States
City	Los Angeles
Period	25/06/18 → 29/06/18
Internet address	http://acm-stoc.org/stoc2018/

Keywords / Materials (for Non-textual outputs)

Necklace Splitting
PPA-Completeness
Consensus-Halving

Access to Document

10.1145/3188745.3188880Licence: All Rights Reserved

https://dl.acm.org/doi/10.1145/3188745.3188880Licence: All Rights Reserved

Cite this

@inproceedings{8249ab3cd0b94483a891f1b9c1864e0a,

title = "Consensus Halving is PPA-Complete",

abstract = "We show that the computational problem Consensus Halving is PPA-Complete, the first PPA-Completeness result for a problem whose definition does not involve an explicit circuit. We also show that an approximate version of this problem is polynomial-time equivalent to Necklace Splitting, which establishes PPAD-hardness for Necklace Splitting and suggests that it is also PPA-Complete.",

keywords = "Necklace Splitting, PPA-Completeness, Consensus-Halving",

author = "Aris Filos-Ratsikas and Goldberg, {Paul W.}",

year = "2018",

month = jun,

day = "20",

doi = "10.1145/3188745.3188880",

language = "English",

series = "STOC 2018",

publisher = "Association for Computing Machinery, Inc",

pages = "51–64",

editor = "Ilias Diakonikolas and David Kempe and Monika Henzinger",

booktitle = "Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing",

note = "50th Annual ACM Symposium on the Theory of Computing, STOC 2018 ; Conference date: 25-06-2018 Through 29-06-2018",

url = "http://acm-stoc.org/stoc2018/",

}

Filos-Ratsikas, A & Goldberg, PW 2018, Consensus Halving is PPA-Complete. in I Diakonikolas, D Kempe & M Henzinger (eds), Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2018, Association for Computing Machinery, Inc, New York, NY, USA, pp. 51–64, 50th Annual ACM Symposium on the Theory of Computing, Los Angeles, California, United States, 25/06/18. https://doi.org/10.1145/3188745.3188880

Consensus Halving is PPA-Complete. / Filos-Ratsikas, Aris; Goldberg, Paul W.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Ilias Diakonikolas; David Kempe; Monika Henzinger. New York, NY, USA: Association for Computing Machinery, Inc, 2018. p. 51–64 (STOC 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Consensus Halving is PPA-Complete

AU - Filos-Ratsikas, Aris

AU - Goldberg, Paul W.

PY - 2018/6/20

Y1 - 2018/6/20

N2 - We show that the computational problem Consensus Halving is PPA-Complete, the first PPA-Completeness result for a problem whose definition does not involve an explicit circuit. We also show that an approximate version of this problem is polynomial-time equivalent to Necklace Splitting, which establishes PPAD-hardness for Necklace Splitting and suggests that it is also PPA-Complete.

AB - We show that the computational problem Consensus Halving is PPA-Complete, the first PPA-Completeness result for a problem whose definition does not involve an explicit circuit. We also show that an approximate version of this problem is polynomial-time equivalent to Necklace Splitting, which establishes PPAD-hardness for Necklace Splitting and suggests that it is also PPA-Complete.

KW - Necklace Splitting

KW - PPA-Completeness

KW - Consensus-Halving

U2 - 10.1145/3188745.3188880

DO - 10.1145/3188745.3188880

M3 - Conference contribution

T3 - STOC 2018

SP - 51

EP - 64

BT - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Diakonikolas, Ilias

A2 - Kempe, David

A2 - Henzinger, Monika

PB - Association for Computing Machinery, Inc

CY - New York, NY, USA

T2 - 50th Annual ACM Symposium on the Theory of Computing

Y2 - 25 June 2018 through 29 June 2018

ER -

Consensus Halving is PPA-Complete

Abstract

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this