Probabilistic Communication Complexity
- 24 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 118-126
- https://doi.org/10.1109/sfcs.1984.715908
Abstract
We study (unbounded error) probabilistic communication complexity. Our new results include -one way and two complexities differ by at most 1 - certain functions like equality and the verification of Hamming distance have upper bounds that are considerably better than their counterparts in deterministic, nondeterministic, or bounded error probabilistic model - there exists a function which requires /spl Omega/(logn) information transfer. As an application, we prove that a certain language requires /spl Omega/(nlogn) time to be recognized by a 1-tape (unbounded error) probabilistic Turing machine. This bound is optimal. (Previous lower bound results [Yao 1] require acceptance by bounded error computation. We believe that this is the first nontrivial lower bound on the time required by unrestricted probabilistic Turing machines.Keywords
This publication has 8 references indexed in Scilit:
- Information Transfer under Different Sets of ProtocolsSIAM Journal on Computing, 1984
- Lower bounds on communication complexityPublished by Association for Computing Machinery (ACM) ,1984
- Lower bounds by probabilistic argumentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Some complexity questions related to distributive computing(Preliminary Report)Published by Association for Computing Machinery (ACM) ,1979
- Oriented matroidsJournal of Combinatorial Theory, Series B, 1978
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- Facing up to arrangements: face-count formulas for partitions of space by hyperplanesMemoirs of the American Mathematical Society, 1975
- Partition of SpaceThe American Mathematical Monthly, 1943