  While exponential separations are known between quantum and randomized
communication complexity for partial functions (Raz, STOC 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 total function,
giving an example exhibiting a power 2.5 gap. We further present a 1.5 power
separation between exact quantum and randomized communication complexity,
improving on the previous ~1.15 separation by Ambainis (STOC 2013). Finally, we
present a nearly optimal quadratic separation between randomized communication
complexity and the logarithm of the partition number, improving upon the
previous best power 1.5 separation due to G\"o\"os, Jayram, Pitassi, and
Watson.
  Our results are the communication analogues of separations in query
complexity proved using the recent cheat sheet framework of Aaronson,
Ben-David, and Kothari (STOC 2016). Our main technical results are randomized
communication and information complexity lower bounds for a family of
functions, called lookup functions, that generalize and port the cheat sheet
framework to communication complexity.
