Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NON-DETERMINISTIC LOGARITHMIC SPACE:
Reports tagged with non-deterministic logarithmic space:
TR09-142 | 17th December 2009
Aaron Potechin

Bounds on Monotone Switching Networks for Directed Connectivity

Revisions: 1

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

more >>>



ISSN 1433-8092 | Imprint