Separations in query complexity using cheat sheets.

Scott Aaronson, Shalev Ben-David, Robin Kothari

Browse the full STOC paper archive.