Probabilistic communication complexity of Boolean relations
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 562-567
- https://doi.org/10.1109/sfcs.1989.63535
Abstract
The authors demonstrate an exponential gap between deterministic and probabilistic complexity and between the probabilistic complexity of monotonic and nonmonotonic relations. They then prove, as their main result, an Omega ((log n)/sup 2/) bound on the probabilistic communication complexity of monotonic st-connectivity. From this they deduce that every nonmonotonic NC/sup 1/ circuit for st-connectivity requires a constant fraction of negated input variables.Keywords
This publication has 3 references indexed in Scilit:
- The Probabilistic Communication Complexity of Set IntersectionSIAM Journal on Discrete Mathematics, 1992
- Monotone circuits for connectivity require super-logarithmic depthPublished by Association for Computing Machinery (ACM) ,1988
- Some complexity questions related to distributive computing(Preliminary Report)Published by Association for Computing Machinery (ACM) ,1979