Summary: A combinatorial interpretation of Berkowitz's algorithm is presented. Berkowitz's algorithm is the fastest known parallel algorithm for computing the characteristic polynomial of a matrix. The combinatorial interpretation is based on "loop covers" introduced by Valiant, and "clow sequences", defined by Mahajan and Vinay. Clow sequences turn out to capture very succinctly the computations performed by Berkowitz's algorithm, which otherwise are quite difficult to analyze. The main contribution of this paper is a proof of correctness of Berkowitz's algorithm in terms of clow sequences.

65F30, 11Y16

berkowitz's algorithm, clow sequences, computational and proof complexity, parallel algorithms, characteristic polynomial