Bounds on monotone switching networks for directed connectivity

2009/11/03 by Potechin, Aaron · 1 citation
#Computational Complexity (cs.CC) #F.1.1 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.0911.0664

Abstract

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))).

Cited by

• A Quantum Time-Space Tradeoff for Directed st-Connectivity

Related

• Monotone switching networks for directed connectivity are strictly more powerful than certain-knowledge switching networks
• Improved upper and lower bound techniques for monotone switching networks for directed connectivity
• Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees
• CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
• Improved Monotone Circuit Depth Upper Bound for Directed Graph Reachability