  We study the communication complexity of incentive compatible
auction-protocols between a monopolist seller and a single buyer with a
combinatorial valuation function over $n$ items. Motivated by the fact that
revenue-optimal auctions are randomized [Tha04,MV10,BCKW10,Pav11,HR15] (as well
as by an open problem of Babaioff, Gonczarowski, and Nisan [BGN17]),we focus on
the randomized communication complexity of this problem (in contrast to most
prior work on deterministic communication). We design simple, incentive
compatible, and revenue-optimal auction-protocols whose expected communication
complexity is much (in fact infinitely) more efficient than their deterministic
counterparts. We also give nearly matching lower bounds on the expected
communication complexity of approximately-revenue-optimal auctions. These
results follow from a simple characterization of incentive compatible
auction-protocols that allows us to prove lower bounds against randomized
auction-protocols. In particular, our lower bounds give the first
approximation-resistant, exponential separation between communication
complexity of incentivizing vs implementing a Bayesian incentive compatible
social choice rule, settling an open question of Fadel and Segal [FS09].
