  We study a central problem in Algorithmic Mechanism Design: constructing
truthful mechanisms for welfare maximization in combinatorial auctions with
submodular bidders. Dobzinski, Nisan, and Schapira provided the first mechanism
that guarantees a non-trivial approximation ratio of $O(\log^2 m)$ [STOC'06],
where $m$ is the number of items. This was subsequently improved to $O(\log
m\log \log m)$ [Dobzinski, APPROX'07] and then to $O(\log m)$ [Krysta and
Vocking, ICALP'12].
  In this paper we develop the first mechanism that breaks the logarithmic
barrier. Specifically, the mechanism provides an approximation ratio of
$O(\sqrt {\log m})$. Similarly to previous constructions, our mechanism uses
polynomially many value and demand queries, and in fact provides the same
approximation ratio for the larger class of XOS (a.k.a. fractionally
subadditive) valuations.
  We also develop a computationally efficient implementation of the mechanism
for combinatorial auctions with budget additive bidders. Although in general
computing a demand query is NP-hard for budget additive valuations, we observe
that the specific form of demand queries that our mechanism uses can be
efficiently computed when bidders are budget additive.
