Query Complexity, Communication Complexity, and Cheat Sheets
February 15, 2017
I will explain the cheat sheet technique in query complexity, and show how to use it to get a power 2.5 separation between classical and quantum computation (beating the quadratic speedup of Grover search). I'll then discuss the connections between query and communication complexity, and present recent applications of the cheat sheet technique in the communication complexity setting.