Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR17-118 | 24th April 2018 18:18

Octahedral Tucker is PPA-Complete


Revision #1
Authors: Xiaotie Deng, Zhe Feng, rucha Kulkarni
Accepted on: 24th April 2018 18:18
Downloads: 968


\OctahedralTucker (a special case of the celebrated \Tucker problem) is the natural computational problem based on Octahedral Tucker's lemma, a classical statement from algebraic topology. Like many fixed point results, this problem has been central to proving several important results from diverse fields of theoretical computer science.~\cite{AWT,SS,Mat,FT}. Resolving the complexity of the natural computational problem associated with it was an important open question, also raised in~\cite{DP,ABB}. \ppa (Polynomial Partity Argument on Graphs) is a complexity class defined in ~\cite{CP}. Computational versions of Tucker's lemma and the Borsuk-Ulam theorem were conjectured to be ideal candidates for \ppac problems, as many problems thought to belong in \ppa were reduced from these. While there has been some progress in finding \ppac problems~\cite{FG,alg_ppa,ABB,Deng}, including \GTwoDTucker\footnote{\textbf{In the rest of the whole paper, for simplifying presentation, $n$-D means $n$-dimensional.}}, the $2$-dimensional version based on Tucker's lemma, the $n$-dimensional \OctahedralTucker problem has evaded resolution.

In this paper, we resolve this decade old open question by proving $n$-dimensional \OctahedralTucker \ppac.
Our reductions also contribute two stand-alone folding techniques, \textit{Fold} and \textit{Wrap}, which are novel as far as we know and could be of broader interest. Additionally, during the reduction process, we define a new \ppac problem \GenOctTucker, another computational problem based on Tucker's lemma that generalizes \OctahedralTucker, adding to the growing list of \ppac problems.


TR17-118 | 20th July 2017 08:25

Octahedral Tucker is PPA-Complete

Authors: Xiaotie Deng, Zhe Feng, Rucha Kulkarni
Publication: 30th July 2017 15:18
Downloads: 1230


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 ${\pm i:i = 1, 2,..., n}$ computed using a polynomial size logic circuit which is also a component of the input. Given that antipodal vertices are assigned complementary colors, there is always an edge (equivalently, a $1$-simplex of the triangulation) for which the two adjacent vertices are assigned complementary colors. The computational complexity to find one has been an outstanding challenging problem. In this paper, we resolve this problem by proving Octahedral Tucker to be PPA-complete.

ISSN 1433-8092 | Imprint