Given a directed graph as input, we show how to efficiently find a shortest (directed, simple)
cycle on an even number of vertices. As far as we know, no polynomial-time algorithm was …

We introduce two-sorted theories in the style of [CN10] for the complexity classes\oplusL and
DET, whose complete problems include determinants over Z2 and Z, respectively. We then …

We present a parallel algorithm for permanent mod 2^ k of a matrix of univariate integer
polynomials. It places the problem in ParityL subset of NC^ 2. This extends the techniques of …

Reachability and Matching are two fundamental graph-theoretic problems that are of prime
interest in Algorithms and Complexity Theory. Over the decades, these two problems have …

We initiate the study of space complexity of certain optimization problems restricted to planar
graphs. We provide upper bounds and hardness results in space complexity for some of …

Motivated by the recent result of [EJT10] showing that MSO properties are Logspace
computable on graphs of bounded tree-width, we consider the complexity of computing the …

In this report, we survey papers on disjoint paths and cycles, which include Björklund and
Husfeldt's algorithm for finding shortest 2-disjoint paths in undirected graphs [BH19] and …

From the introduction:“This paper is a contribution to bounded reverse mathematics, that part
of proof complexity concerned with determining the computational complexity of concepts …

The purpose of this article is to survey several useful properties of planar graphs that can be
exploited specifically in the context of space bounded computation to obtain efficient …

Given linear representations M1 and M2 of matroids over a field F, we consider the problem
(denoted by ECLR [F]) of checking if M1 and M2 represent the same matroid over F. When …