Title: Lower bounds for one-way probabilistic communication complexity
Abstract: We prove three different types of complexity lower bounds for the one-way unbounded-error and bounded-error error probabilistic communication protocols for boolean functions. The lower bounds are proved for arbitrary boolean functions in the common way in terms of the deterministic communication complexity of functions and in terms of the notion “probabilistic communication characteristic” that we define. Our lower bounds are good enough for proving proper hierarchies for various one-way probabilistic communication complexity classes (namely for unbounded error probabilistic communication, for bounded error probabilistic communication, and for errors of probabilistic communication).
Publication Year: 1993
Publication Date: 1993-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 17
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot