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