The Linear-Array Conjecture in Communication Complexity is False.

Eyal Kushilevitz, Nathan Linial, Rafail Ostrovsky

Browse the full STOC paper archive.