  We consider the problem of designing a revenue-maximizing auction for a
single item, when the values of the bidders are drawn from a correlated
distribution. We observe that there exists an algorithm that finds the optimal
randomized mechanism that runs in time polynomial in the size of the support.
We leverage this result to show that in the oracle model introduced by Ronen
and Saberi [FOCS'02], there exists a polynomial time truthful in expectation
mechanism that provides a $(\frac 3 2+\epsilon)$-approximation to the revenue
achievable by an optimal truthful-in-expectation mechanism, and a polynomial
time deterministic truthful mechanism that guarantees $\frac 5 3$ approximation
to the revenue achievable by an optimal deterministic truthful mechanism.
  We show that the $\frac 5 3$-approximation mechanism provides the same
approximation ratio also with respect to the optimal truthful-in-expectation
mechanism. This shows that the performance gap between truthful-in-expectation
and deterministic mechanisms is relatively small. En route, we solve an open
question of Mehta and Vazirani [EC'04].
  Finally, we extend some of our results to the multi-item case, and show how
to compute the optimal truthful-in-expectation mechanisms for bidders with more
complex valuations.
