We study \emph{entropy flattening}: Given a circuit \mathcal{C}_X implicitly describing an n-bit source X (namely, X is the output of \mathcal{C}_X on a uniform random input), construct another circuit \mathcal{C}_Y describing a source Y such that (1) source Y is nearly \emph{flat} (uniform on its support), and (2) the Shannon ... more >>>

While exponential separations are known between quantum and randomized communication complexity for partial functions, e.g. Raz [1999], the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized
communication complexity for a ... more >>>