  We show new lower bounds in the \emph{Merlin-Arthur} (MA) communication model
and the related \emph{annotated streaming} or stream verification model. The MA
communication model is an enhancement of the classical communication model,
where in addition to the usual players Alice and Bob, there is an all-powerful
but untrusted player Merlin who knows their inputs and tries to convince them
about the output. Most functions have MA protocols with total communication
significantly smaller than what would be needed without Merlin. We focus on the
online MA (OMA) model, which is the MA analogue of one-way communication, and
introduce the notion of \emph{non-trivial-OMA} complexity of a function. This
is the minimum total communication needed by any non-trivial OMA protocol
computing that function, where a trivial OMA protocol is one where Alice sends
Bob roughly as many bits as she would have sent without Merlin. We prove a
lower bound on the non-trivial-OMA complexity of a natural function
\emph{Equals-Index} (basically the well-known Index problem on large domains)
and identify it as a canonical problem for proving strong lower bounds on this
complexity: reductions from it (i) reproduce and/or improve upon the lower
bounds for all functions that were previously known to have large
non-trivial-OMA complexity, (ii) exhibit the first explicit functions whose
non-trivial-OMA complexity is superlinear, and even exponential, in their
classical one-way complexity, and (iii) show functions on input size $n$ for
which this complexity is as large as $n/\log n$. While exhibiting a function
with $\omega(\sqrt{n})$ (standard) OMA complexity is a longstanding open
problem, we did not even know of any function with $\omega(\sqrt{n})$
non-trivial-OMA complexity. We further extend the lower bounds to a related
streaming model called annotated streaming.
