Some order dimension bounds for communication complexity problems

DOI10.1007/BF01463947MaRDI QIDQ921909zbMATH OpenFDO

Authors U. Faigle, Walter Kern

Publication date 1991

Published in Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

communication complexityordered sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

• Dimension-free bounds and structural results in communication complexity
• The communication complexity of interval orders
• scientific article; zbMATH DE number 2170852
• Communication complexity and linearly ordered sets
• scientific article; zbMATH DE number 4068270
• Lower bounds on communication complexity
• Lower bounds in communication complexity
• Communication Complexity and Lower Bounds on Multilective Computations
• On the ``log rank-conjecture in communication complexity

Cites work

• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 4197419 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• Expressing combinatorial optimization problems by linear programs
• Partially Ordered Sets

Cited in

(8)

• A connectionist approach to the quadratic assignment problem
• scientific article; zbMATH DE number 2170852 (Why is no real title available?)
• Deterministic communication vs. partition number
• The communication complexity of interval orders
• Communication Lower Bounds Via the Chromatic Number
• Ordered biclique partitions and communication complexity problems
• Dimension-free bounds and structural results in communication complexity
• Some improved bounds on communication complexity via new decomposition of cliques

This page was built for publication: Some order dimension bounds for communication complexity problems

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