  We show that every universally truthful randomized mechanism for
combinatorial auctions with submodular valuations that provides $m^{\frac 1 2
-\epsilon}$ approximation to the social welfare and uses value queries only
must use exponentially many value queries, where $m$ is the number of items. In
contrast, ignoring incentives there exist constant ratio approximation
algorithms for this problem. Our approach is based on a novel \emph{direct
hardness} approach and completely skips the notoriously hard characterization
step. The characterization step was the main obstacle for proving impossibility
results in algorithmic mechanism design so far.
  We demonstrate two additional applications of our new technique: (1) an
impossibility result for universally-truthful polynomial time flexible
combinatorial public projects and (2) an impossibility result for
truthful-in-expectation mechanisms for exact combinatorial public projects. The
latter is the first result that bounds the power of polynomial-time truthful in
expectation mechanisms in any setting.
