  In the consensus halving problem we are given n agents with valuations over
the interval $[0,1]$. The goal is to divide the interval into at most $n+1$
pieces (by placing at most n cuts), which may be combined to give a partition
of $[0,1]$ into two sets valued equally by all agents. The existence of a
solution may be established by the Borsuk-Ulam theorem. We consider the task of
computing an approximation of an exact solution of the consensus halving
problem, where the valuations are given by distribution functions computed by
algebraic circuits. Here approximation refers to computing a point that
$\varepsilon$-close to an exact solution, also called strong approximation. We
show that this task is polynomial time equivalent to computing an approximation
to an exact solution of the Borsuk-Ulam search problem defined by a continuous
function that is computed by an algebraic circuit.
  The Borsuk-Ulam search problem is the defining problem of the complexity
class BU. We introduce a new complexity class BBU to also capture an
alternative formulation of the Borsuk-Ulam theorem from a computational point
of view. We investigate their relationship and prove several structural results
for these classes as well as for the complexity class FIXP.
