Computational complexity: Counting, evasiveness, and isolation

We present results in three areas of Computational Complexity Theory: (1) Complexity of Counting, (2) Decision Tree Complexity, and (3) Space Complexity.;A recurrent theme is to exploit the connections of computational models to areas of mathematics including Algebraic Topology, Analytic Number Theory, and Group Theory.;In the first part, we study the complexity of computing the Determinant and the Permanent of a matrix modulo a constant power of 2. We also study the complexity of counting and modular counting of Spanning Trees and Perfect Matchings in general as well as in planar graphs. We use tools from Algebraic Topology to get a surprising upper bound on the complexity of counting spanning trees in planar graphs modulo a constant power of 2.;In the second part, we study the decision tree complexity of monotone graph properties. Building on a topological approach of Kahn, Saks, and Sturtevant, we solve new special cases of the Evasiveness Conjecture: a notorious problem that has been open for nearly four decades. We make connections to Analytic Number Theory by constructing new group actions suitable for the topological approach.;In the third part, we study questions related to Space Complexity of computing a perfect matching in planar graphs and link the study of similar questions in planar graphs to relations between complexity classes like NL and ⊕L.