  We consider a revenue-maximizing single seller with $m$ items for sale to a
single buyer whose value $v(\cdot)$ for the items is drawn from a known
distribution $D$ of support $k$. A series of works by Cai et al. establishes
that when each $v(\cdot)$ in the support of $D$ is additive or unit-demand (or
$c$-demand), the revenue-optimal auction can be found in
$\operatorname{poly}(m,k)$ time.
  We show that going barely beyond this, even to matroid-based valuations (a
proper subset of Gross Substitutes), results in strong hardness of
approximation. Specifically, even on instances with $m$ items and $k \leq m$
valuations in the support of $D$, it is not possible to achieve a
$1/m^{1-\varepsilon}$-approximation for any $\varepsilon>0$ to the
revenue-optimal mechanism for matroid-based valuations in (randomized)
poly-time unless NP $\subseteq$ RP (note that a $1/k$-approximation is
trivial).
  Cai et al.'s main technical contribution is a black-box reduction from
revenue maximization for valuations in class $\mathcal{V}$ to optimizing the
difference between two values in class $\mathcal{V}$. Our main technical
contribution is a black-box reduction in the other direction (for a wide class
of valuation classes), establishing that their reduction is essentially tight.
