Probabilistic communication complexity of Boolean relations

Ran Raz, Avi Wigderson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

29 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages562-567
Number of pages6
ISBN (Print)0818619821, 9780818619823
DOIs
StatePublished - 1989
Externally publishedYes
Event30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA
Duration: Oct 30 1989Nov 1 1989

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

Other30th Annual Symposium on Foundations of Computer Science
CityResearch Triangle Park, NC, USA
Period10/30/8911/1/89

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Probabilistic communication complexity of Boolean relations'. Together they form a unique fingerprint.

Cite this