  We consider truthful combinatorial auctions with items $M = [m]$ for sale to
$n$ bidders, where each bidder $i$ has a private monotone valuation $v_i : 2^M
\to R_+$. Among truthful mechanisms, maximal-in-range (MIR) mechanisms achieve
the best-known approximation guarantees among all poly-communication
deterministic truthful mechanisms in all previously-studied settings. Our work
settles the communication necessary to achieve any approximation guarantee via
an MIR mechanism. Specifically:
  Let MIRsubmod$(m,k)$ denote the best approximation guarantee achievable by an
MIR mechanism using $2^k$ communication between bidders with submodular
valuations over $m$ items. Then for all $k = \Omega(\log(m))$, MIRsubmod$(m,k)
= \Omega(\sqrt{m/(k\log(m/k))})$. When $k = \Theta(\log(m))$, this improves the
previous best lower bound for poly-comm. MIR mechanisms from
$\Omega(m^{1/3}/\log^{2/3}(m))$ to $\Omega(\sqrt{m}/\log(m))$. We also have
MIRsubmod$(m,k) = O(\sqrt{m/k})$. Moreover, our mechanism is optimal w.r.t. the
value query and succinct representation models. When $k = \Theta(\log(m))$,
this improves the previous best approximation guarantee for poly-comm. MIR
mechanisms from $O(\sqrt{m})$ to $O(\sqrt{m/\log(m)})$.
  Let also MIRgen$(m,k)$ denote the best approximation guarantee achievable by
an MIR mechanism using $2^k$ communication between bidders with general
valuations over $m$ items. Then for all $k = \Omega(\log(m))$, MIRgen$(m,k) =
\Omega(m/k)$. When $k = \Theta(\log(m))$, this improves the previous best lower
bound for poly-comm. MIR mechanisms from $\Omega(m/\log^2(m))$ to
$\Omega(m/\log(m))$. We also have MIRgen$(m,k) = O(m/k)$. Moreover, our
mechanism is optimal w.r.t. the value query and succinct representation models.
When $k = \Theta(\log(m))$, this improves the previous best approximation
guarantee for poly-comm. MIR mechanisms from $O(m/\sqrt{\log(m)})$ to
$O(m/\log(m))$.
