Rounds in Communication Complexity Revisited
From MaRDI portal
Publication:4037694
DOI10.1137/0222016zbMath0767.68066OpenAlexW2051019379MaRDI QIDQ4037694
Publication date: 16 May 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0222016
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Circuits, networks (94C99) Measures of information, entropy (94A17) Communication theory (94A05)
Related Items (29)
Hellinger volume and number-on-the-forehead communication complexity ⋮ An adaptivity hierarchy theorem for property testing ⋮ Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance ⋮ Lower bounds for one-way probabilistic communication complexity and their application to space complexity ⋮ Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions ⋮ Superlinear lower bounds for multipass graph processing ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ Extension of the hierarchy for \(k\)-OBDDs of small width ⋮ Hadamard tensors and lower bounds on multiparty communication complexity ⋮ Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity ⋮ Energy-efficient distributed algorithms for synchronous networks ⋮ Privacy in non-private environments ⋮ Unnamed Item ⋮ List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise ⋮ Optimal collapsing protocol for multiparty pointer jumping ⋮ Unexpected upper bounds on the complexity of some communication games ⋮ Reversal complexity revisited ⋮ The NOF multiparty communication complexity of composed functions ⋮ The Hardness of Median in the Synchronized Bit Communication Model ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ New lower bounds and hierarchy results for restricted branching programs ⋮ The communication complexity of pointer chasing ⋮ Trading Bit, Message, and Time Complexity of Distributed Algorithms ⋮ On data structures and asymmetric communication complexity ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs ⋮ Verifiable Stream Computation and Arthur--Merlin Communication ⋮ Pointer chasing via triangular discrimination ⋮ Computing (and Life) Is All about Tradeoffs
This page was built for publication: Rounds in Communication Complexity Revisited
