Probabilistic Communication Complexity (Preliminary Version)

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.

Authors

• Ramamohan Paturi
• Janos Simon

Keywords

• Complexity theory
• Protocols
• Distributed computing
• Probability distribution
• Concatenated codes
• Computer science
• Computer errors
• Hamming distance
• Upper bound
• Power measurement
• Complex Communication
• Information Transfer
• Outcome Events
• Probability Calculation
• Turing Machine
• Sequence Of Bits
• Matrix M