Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-142 | 14th August 2010 08:16

Bounds on Monotone Switching Networks for Directed Connectivity

RSS-Feed




Revision #1
Authors: Aaron Potechin
Accepted on: 14th August 2010 08:16
Downloads: 3254
Keywords: 


Abstract:

We prove that any monotone switching network solving directed connectivity on $N$ vertices must have size at least $N^{\Omega(\log N)}$


Paper:

TR09-142 | 17th December 2009 23:50

Bounds on Monotone Switching Networks for Directed Connectivity





TR09-142
Authors: Aaron Potechin
Publication: 20th December 2009 20:57
Downloads: 3705
Keywords: 


Abstract:

We prove that any monotone switching network solving directed connectivity on $N$ vertices must have size $N^{\Omega(\log N)}$



ISSN 1433-8092 | Imprint