3

Sorry, this is clearly unlikely. Otherwise, it would be possible to use the algorithm to solve any NL\poly problem in NC1 via a reduction to evaluating the determinant of a Hessenberg matrix over a sufficiently large field. The reduction appears as Lemma 3 (and related discussion) in "Perfect constant-round secure computation via perfect randomizing ...


1

This is very similar to overlaps of gene sequence in genome assembly. Chapter 4 of Ananth's thesis. In parallel you search for promising pairs and maintain a distributed union find data structure. See Tarjan and Vishkin for their hook and shortcut algorithm to collapse the connected components. Also, you can try recent DeBrujin graph methods on 64 bit row ...


Only top voted, non community-wiki answers of a minimum length are eligible