  We consider the $\varepsilon$-Consensus-Halving problem, in which a set of
heterogeneous agents aim at dividing a continuous resource into two (not
necessarily contiguous) portions that all of them simultaneously consider to be
of approximately the same value (up to $\varepsilon$). This problem was
recently shown to be PPA-complete, for $n$ agents and $n$ cuts, even for very
simple valuation functions. In a quest to understand the root of the complexity
of the problem, we consider the setting where there is only a constant number
of agents, and we consider both the computational complexity and the query
complexity of the problem.
  For agents with monotone valuation functions, we show a dichotomy: for two
agents the problem is polynomial-time solvable, whereas for three or more
agents it becomes PPA-complete. Similarly, we show that for two monotone agents
the problem can be solved with polynomially-many queries, whereas for three or
more agents, we provide exponential query complexity lower bounds. These
results are enabled via an interesting connection to a monotone Borsuk-Ulam
problem, which may be of independent interest. For agents with general
valuations, we show that the problem is PPA-complete and admits exponential
query complexity lower bounds, even for two agents.
