Bounds on monotone switching networks for directed connectivity

preprint2016arXivOpen access

We separate monotone analogues of L and NL by proving that any monotone switching network solving directed connectivity on $n$ vertices must have size at least $n^(Ω(\lg(n)))$ .

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Write a reviewWrite

No reviews yet.

Add a commentWrite

No comments yet.

Bounds on monotone switching networks for directed connectivity

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0