The linear-array conjecture in communication complexity is false

DOI10.1007/s004930050054zbMath0929.68129WikidataQ122887971 ScholiaQ122887971MaRDI QIDQ1125618

Rafail Ostrovsky, Nathan Linial, Eyal Kushilevitz

Publication date: 8 December 1999

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s004930050054

zbMATH Keywords

linear-array conjecture

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68W10: Parallel algorithms in computer science

94A05: Communication theory