The complexity of finding a Borsuk-Ulam point

Question

The Borsuk-Ulam theorem says that for every continuous odd function $g$ from an n-sphere into Euclidean n-space, there is a point $x_0$ such that $g(x_0)=0$.

Simmons and Su (2002) describe a method to approximate the point $x_0$ using Tucker's lemma. However, it is not clear what the run-time complexity of their method is.

Suppose we are given an oracle for the function $g$ and an approximation factor $\epsilon>0$. What is the run-time complexity (as a function of $n$) of:

1. Finding a point $x$ such $|g(x)|<\epsilon$?
2. Finding a point $x$ such that the $|x-x_0|<\epsilon$, when $x_0$ is a point satisfying $g(x_0)=0$?

Answer 1

Papadimitriou showed that a version of this problem is PPAD-complete in the paper introducing that class, "On the complexity of the parity argument and other inefficient proofs of existence".

His formulation of the problem is:

Borsuk-Ulam. Given an integer n and a Turing machine computing for each point $P=(x_1,\dots,x_d)$ with $-n\leq x_i\leq n$ and $\max_{|x_i|}=n$ (the surface of the $L_1$ sphere), a function $f(p)$ with $f(p) \leq \frac{1}{Kn}$. Find an $x$ with $|f(x) - f( - x)| \leq \frac{1}{n^2}$.

(Sidenote -- many times when you see a fixed-point type of theorem, PPAD is a good guess for the complexity of finding it...)

Answer 2

How is the oracle given and what do we know about $g$? If the oracle is black-box and we only know that $g$ is continuous odd, then already for $n=1$ we might require infinitely many questions...

If the oracle is given by some Turing-machine, then you get that your problem is

1. FIXP-complete,

2. PPA-complete,

where the size of the input is length of $\epsilon$. For an intro into these, see http://homepages.inf.ed.ac.uk/kousha/dagstuhl14-etessami-tutorial-equilibrium.pdf and here where they prove PPA-completeness, correcting the earlier incorrect claim from Papadimitriou that it is in PPAD: https://doi.org/10.1016/j.jcss.2019.09.002