Different Modes of Communication

DOI10.1137/0222057MaRDI QIDQ3142585zbMATH OpenOpenAlexFDO

Authors Bernd Halstenberg, Rüdiger Reischuk

Publication date 13 March 1994

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0222057

zbMATH Keywords

\(k\)-round protocolsprobabilistic protocols

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Distributed algorithms (68W15) Communication theory (94A05)

Recommendations

• Information Transfer under Different Sets of Protocols
• Probabilistic communication complexity
• Rounds in Communication Complexity Revisited
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• Lower bounds on communication complexity

Cited in

(17)

• Lower bounds on communication complexity
• Approximation of boolean functions by combinatorial rectangles
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• Communication via intermediaries
• Computing (and Life) Is All about Tradeoffs
• Information Transfer under Different Sets of Protocols
• Determinism vs. Nondeterminism in Multiparty Communication Complexity
• Lower bounds for one-way probabilistic communication complexity
• Half-duplex communication complexity
• Probabilistic communication complexity
• Variants of spreading messages
• One-way communication complexity of symmetric Boolean functions.
• The communication complexity of pointer chasing
• Around the log-rank conjecture
• New lower bounds and hierarchy results for restricted branching programs
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• New bounds on the half-duplex communication complexity

This page was built for publication: Different Modes of Communication

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