Berkowitz's Algorithm and Clow Sequences

We present a combinatorial interpretation of Berkowitz’s algorithm. Berkowitz’s algorithm is the fastest known parallel algorithm for computing the characteristic polynomial of a matrix. Our combinatorial interpretation is based on loop covers'' introduced by Valiant, and clow sequences.‘’ Clow sequences turn out to capture very succinctly the computations performed by Berkowitz’s algorithm, which otherwise is quite difficult to analyze. The main contribution of this paper is a proof of correctness of Berkowitz’s algorithm in terms of clow sequences.