The linear-array conjecture in communication complexity is false

DOI10.1007/S004930050054MaRDI QIDQ1125618zbMATH OpenOpenAlexWikidataFDO

Authors Eyal Kushilevitz, Rafail Ostrovsky, 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)

Recommendations

• scientific article; zbMATH DE number 1256713
• scientific article; zbMATH DE number 1559553
• Probabilistic communication complexity

Cited in

(10)

• Ordered biclique partitions and communication complexity problems
• Some improved bounds on communication complexity via new decomposition of cliques
• scientific article; zbMATH DE number 1256713 (Why is no real title available?)
• scientific article; zbMATH DE number 1559553 (Why is no real title available?)
• A counterexample to the Alon-Saks-Seymour conjecture and related problems
• Deterministic communication vs. partition number
• The Log-Approximate-Rank Conjecture Is False
• Mathematical Foundations of Computer Science 2005
• On the communication complexity of finding a king in a tournament
• The lazy adversary conjecture fails

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1125618)