ECCC-Report TR17-118https://eccc.weizmann.ac.il/report/2017/118Comments and Revisions published for TR17-118en-usTue, 24 Apr 2018 18:18:27 +0300
Revision 1
| Octahedral Tucker is PPA-Complete |
Xiaotie Deng,
Zhe Feng,
rucha Kulkarni
https://eccc.weizmann.ac.il/report/2017/118#revision1\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. Tue, 24 Apr 2018 18:18:27 +0300https://eccc.weizmann.ac.il/report/2017/118#revision1
Paper TR17-118
| Octahedral Tucker is PPA-Complete |
Xiaotie Deng,
Zhe Feng,
Rucha Kulkarni
https://eccc.weizmann.ac.il/report/2017/118The 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.Sun, 30 Jul 2017 15:18:03 +0300https://eccc.weizmann.ac.il/report/2017/118