The complexity of finding a Borsuk-Ulam point
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...)