Many commonly-used auction mechanisms are ``maximal-in-range''. We show that any maximal-in-range mechanism for n bidders and m items cannot both approximate the social welfare with a ratio better than \min(n, m^\eta) for any constant \eta < 1/2 and run in polynomial time, unless NP \subseteq P/poly. This significantly improves upon ... more >>>