High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich

The Borsuk-Ulam theorem states that every continuous odd function $f: {\mathcal{S}}^{n} \rightarrow \mathbb{R}^{n}$ must have a zero, i.e., an $x \in {\mathcal{S}}^{n}$ such that $f(x)=0$. While such a zero is guaranteed to exist, finding it is known to be computationally intractable: it is PPAcomplete already for n = 2. In this work, we show that the problem remains just as hard even if the function is mapping from a higher to a lower dimensional space. Namely, we prove that it is PPA-complete to find a zero of $f: {\mathcal{S}}^{k} \rightarrow \mathbb{R}^{n}$ for any constants $k \geq n \geq 2$. This result has very appealing consequences for other flagship PPA-complete problems such as Tucker, Consensus Halving, and Ham Sandwich. For example, in the Consensus Halving problem from fair division, we show that finding a partition that satisfies three agents with monotone valuations is PPA-complete, even if we allow any arbitrarily large constant number of cuts.