The linear-array conjecture in communication complexity is false

DOI10.1007/s004930050054zbMath0929.68129OpenAlexW2610838164WikidataQ122887971 ScholiaQ122887971MaRDI QIDQ1125618

Rafail Ostrovsky, Eyal Kushilevitz, Nathan Linial

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

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10) Communication theory (94A05)

Related Items (4)

Some improved bounds on communication complexity via new decomposition of cliques ⋮ Deterministic Communication vs. Partition Number ⋮ A counterexample to the Alon-Saks-Seymour conjecture and related problems ⋮ Ordered biclique partitions and communication complexity problems

This page was built for publication: The linear-array conjecture in communication complexity is false