The greedy sequential algorithm for maximal independent set (MIS) loops over the vertices
in an arbitrary order adding a vertex to the resulting set if and only if no previous neighboring …

It is shown that black-box derandomization of polynomial identity testing (PIT) is essentially
equivalent to derandomization of Noether's Normalization Lemma for explicit algebraic …

We show that, for k constant, k-tree isomorphism can be decided in logarithmic space by
giving an O (klogn) space canonical labeling algorithm. The algorithm computes a unique …

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 …

In this paper, we propose a silent self-stabilizing asynchronous distributed algorithm for
constructing a kclustering of any connected network with unique IDs. Our algorithm …

Deciding equivalence of probabilistic automata is a key problem for establishing various
behavioural and anonymity properties of probabilistic systems. In recent experiments a …

In 1990 Subramanian defined the complexity class CC as the set of problems log-space
reducible to the comparator circuit value problem (CCV). He and Mayr showed that …

In this paper we describe the randomized parallel algorithm proposed by Blelloch et
al.[BFS12] to compute a Maximal Independent Set (MIS) of a given graph. We implemented …

Let G=(V, E) be an undirected graph. An independent set of G is a subset I of V such that no
two vertex in I are adjacent in G. A Maximal Independent Set (MIS) of G is an independent …

We consider a new notion of circuit uniformity based on the concept of rational relations,
called Rational-uniformity and denoted Rat. Our goal is to prove it is sharper than DLogTime …