On multi-partition communication complexity
type: Item
instance of: scholarly article
title: On multi-partition communication complexity
zbMATH Open document ID: 1073.68030
author: Pavol Ďuriš
author: Martin Sauerhoff
author: Georg Schnitger
author: Juraj Hromkovič
author: Stasys Jukna
published in: Information and Computation
publication date: 2004-11-12T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68M12
zbMATH DE Number: 2115409
zbMATH Keywords: Computational complexity
zbMATH Keywords: Multi-partition communication complexity
zbMATH Keywords: Non-obliviousness
zbMATH Keywords: Lower bounds
zbMATH Keywords: Complexity hierarchy
zbMATH Keywords: Read-once branching programs
zbMATH Keywords: \(k\)-partition protocols
MaRDI profile type: Publication
full work available at URL: j.ic.2004.05.002
OpenAlex ID: W2025380793
cites work: Meanders and their applications in lower bounds arguments
cites work: Time-space tradeoffs for branching programs
cites work: Time-space trade-off lower bounds for randomized computation of decision problems
cites work: On lower bounds for read-\(k\)-times branching programs
cites work: Bounds on tradeoffs between randomness and communication complexity
cites work: A communication-randomness tradeoff for two-processor systems
cites work: Q4337605
cites work: Q4788609
cites work: Q4501529
cites work: The power of nondeterminism and randomness for oblivious branching programs
cites work: Neither reading few bits twice nor reading illegally helps much
cites work: Q4792910
cites work: Communication Complexity
cites work: Q4146667
cites work: Two-way deterministic finite automata are exponentially more succinct than sweeping automata
cites work: Private vs. common random bits in communication complexity
cites work: Communication complexity
cites work: Nondeterminism and the size of two way finite automata
cites work: New Algorithms for Finding Irreducible Polynomials Over Finite Fields
cites work: Lower bounds on the size of sweeping automata
cites work: Branching Programs and Binary Decision Diagrams
DOI: 10.1016/J.IC.2004.05.002
Recommended article: Q2762506
Recommended article: Partition arguments in multiparty communication complexity
Recommended article: Partition Arguments in Multiparty Communication Complexity
Recommended article: Q5368738
Recommended article: Q4260377
Recommended article: Q3002823
Recommended article: Q4337605
Recommended article: Communication complexity of multi-processor systems
Recommended article: The multiparty communication complexity of set disjointness
description: scientific article; zbMATH DE number 2115409