The complexity of finding a Borsuk-Ulam point 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&gt;0$. What is the run-time complexity (as a function of $n$) of:


Finding a point $x$ such $|g(x)|&lt;\epsilon$?
Finding a point $x$ such that the $|x-x_0|&lt;\epsilon$, when $x_0$ is a point satisfying $g(x_0)=0$?
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...)