Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and important ... more >>>

We show that the reachability problem for directed graphs that are either K_{3,3}-free or K_5-free is in unambiguous log-space, UL \cap coUL. This significantly extends the result of Bourke, Tewari, and Vinodchandran that the reachability problem for directed planar graphs is in UL \cap coUL. Our algorithm decomposes the graphs ... more >>>

The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms, it is in the class AC^1. In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to ... more >>>

The perfect matching problem is known to be in P, in randomized NC, and it is hard for NL. Whether the perfect matching problem is in NC is one of the most prominent open questions in complexity theory regarding parallel computations. Grigoriev and Karpinski studied the perfect matching problem for ... more >>>

We show necessary and sufficient conditions that certain algebraic functions like the rank or the signature of an integer matrix can be computed in GapL. more >>>

We investigate the computational complexity of the minimal polynomial of an integer matrix. We show that the computation of the minimal polynomial is in AC^0(GapL), the AC^0-closure of the logspace counting class GapL, which is contained in NC^2. Our main result is that the problem is hard for GapL (under ... more >>>

We show that the satisfiability problem for bounded error probabilistic ordered branching programs is NP-complete. If the error is very small however (more precisely, if the error is bounded by the reciprocal of the width of the branching program), then we have a polynomial-time algorithm for the satisfiability problem. more >>>

We investigate the computational complexity of the isomorphism problem for one-time-only branching programs (BP1-Iso): on input of two one-time-only branching programs B and B', decide whether there exists a permutation of the variables of B' such that it becomes equivalent to B. Our main result is a two-round interactive proof ... more >>>

We investigate the computational complexity of the Boolean Isomorphism problem (BI): on input of two Boolean formulas F and G decide whether there exists a permutation of the variables of G such that F and G become equivalent. Our main result is a one-round interactive proof for $\overline{BI}$, where the ... more >>>

The classes of languages accepted by nondeterministic polynomial-time Turing machines (NP machines, in short) that have restricted access to an NP oracle --- the machines can ask k queries to the NP oracle and the answer they receive is the number of queries in the oracle language modulo a number ... more >>>