Loading jsMath...
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: 3412
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: 3846
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