Probabilistic communication complexity of Boolean relations
Ran Raz, Avi Wigderson · 1989
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.>