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 …

Existing definitions of the relativizations of NC 1, L and NL do not preserve the inclusions NC
1⊆ L, NL⊆ AC 1. We start by giving the first definitions that preserve them. Here for L and …

A tournament is a graph in which each pair of distinct vertices is connected by exactly one
directed edge. Tournaments are an important graph class, for which isomorphism testing …

The computational model of Quantum Finite Automata has been introduced by multiple
authors (eg [38, 44]) with some variations in definition. The objective of this thesis is to …

Il existe de nombreuses approches développées par la communauté Implicit Computational
Complexity (ICC) permettant d'analyser les ressources nécessaires à la bonne exécution …

We introduce a new type of finite copying parallel rewriting system, ie, grammars with linked
nonterminals, which extend the generative capacity of context-free grammars. They can be …

The notions of weak and strong unambiguity of augmented push-down automata are
considered and related to unambiguities of circuits. In particular we exhibit circuit classes …

We show that several reducibility notions coincide when applied to the Graph Isomorphism
(GI) problem. In particular we show that if a set is many-one logspace reducible to GI, then it …

We characterize the complexity of some natural and important problems in linear algebra. In
particular, we identify natural complexity classes for which the problems of (a) determining if …

Abstract Gottlob,(1993, in\Proceedings, 34th IEEE Symp. on Found. Comput. Sci.," pp. 42
{51), showed that any set recognized by polynomial-size, log-depth trees with queries to …