@inproceedings{bbbcd6aa71264595a4fad22e7ba8f10a,
title = "Probabilistic communication complexity of Boolean relations",
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 Ω((log n)2) bound on the probabilistic communication complexity of monotonic st-connectivity. From this they deduce that every nonmonotonic NC1 circuit for st-connectivity requires a constant fraction of negated input variables.",
author = "Ran Raz and Avi Wigderson",
year = "1989",
doi = "10.1109/sfcs.1989.63535",
language = "English (US)",
isbn = "0818619821",
series = "Annual Symposium on Foundations of Computer Science (Proceedings)",
publisher = "Publ by IEEE",
pages = "562--567",
booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",
note = "30th Annual Symposium on Foundations of Computer Science ; Conference date: 30-10-1989 Through 01-11-1989",
}