6533b85dfe1ef96bd12bdbf2
RESEARCH PRODUCT
Communication complexity in a 3-computer model
Andris Ambainissubject
Theoretical computer scienceGeneral Computer ScienceComputer scienceApplied MathematicsDivergence-from-randomness modelProbabilistic logicComputer Science ApplicationsProbabilistic CTLWorst-case complexityIdentity functionProbabilistic analysis of algorithmsPhysics::Chemical PhysicsCommunication complexityDecision tree modeldescription
It is proved that the probabilistic communication complexity of the identity function in a 3-computer model isO(√n).
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1996-09-01 | Algorithmica |