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

more >>>

Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. ... more >>>