Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with PPA-Completeness:
TR15-120 | 12th July 2015
Xiaotie Deng, Zhe Feng, Zhengyang Liu, Qi Qi

Understanding PPA-Completeness

Revisions: 1

The search complexity classes {\bf PPA} and {\bf PPAD} were proposed by Papadimitriou twenty years ago for characterizing the computational difficulties of many interesting natural search problems. While many members in the complete class of {\bf PPAD}, {\bf PPAD}-completeness, are established in the past twenty years, the understanding of the ... more >>>

TR17-118 | 20th July 2017
Xiaotie Deng, Zhe Feng, Rucha Kulkarni

Octahedral Tucker is PPA-Complete

Revisions: 1

The Octahedral Tucker problem considers an n-dimensional hypergrid of side length two, centered at the origin, triangulated by connecting the origin to all outside vertices (applied recursively on each of the lower dimensional hypergrids passing through their origins at the corresponding reduced dimensions). Each vertex is assigned a color in ... more >>>

ISSN 1433-8092 | Imprint