  Consider an asynchronous system where each node begins with some point in
$\mathbb{R}^m$. Given some fixed $\epsilon > 0$, we wish to have every
nonfaulty node eventually output a point in $\mathbb{R}^m$, where all outputs
are within distance $\epsilon$ of each other, and are within the convex hull of
the original nonfaulty inputs. This problem, when some of the nodes are
adversarial, is known as the ``Byzantine Asynchronous Multidimensional
Approximate Agreement'' problem.
  Previous landmark work by Mendes et al. and Vaidya et al. presented two
solutions to the problem. Both of these solutions require exponential
computation by each node in each round. Furthermore, the work provides a lower
bound showing that it is impossible to solve the task of approximate agreement
if $n\leq (m+2)t$, and thus the protocols assume that $n>(m+2)t$.
  We present a Byzantine Asynchronous Multidimensional Approximate Agreement
protocol in the validated setting of Cachin et al. Our protocol terminates
after a logarithmic number of rounds, and requires only polynomial computation
in each round. Furthermore, it is resilient to $t<\frac{n}{3}$ Byzantine nodes,
which we prove to be optimal in the validated setting. In other words, working
on the task in the validated setting allows us to significantly improve on
previous works in several significant metrics. In addition, the techniques
presented in this paper can easily yield a protocol in the original
non-validated setting which requires exponential computation only in the first
round, and polynomial computation in every subsequent round.
