Berkowitz's algorithm and clow sequences
The author gives a detailed inductive proof of correctness for \textit{S. J. Berkowitz}'s algorithm (BA) [Inf. Process. Lett. 18, 147-150 (1984; Zbl 0541.68019)] in terms of clow (closed walk) sequences defined by \textit{M. Mahajan} and \textit{V. Vinay} [Chic. J. Theor. Comput. Sci. 1997, Article No. 5 (1997; Zbl 0924.68088)], that is, BA computes the coefficients of the characteristic polynomial of a matrix \(A\), \(p_A(x)=\det(xI-A)\), by computing iterated matrix products, and hence it can be formalized in the complexity class NC\(^2\). This class is the class of problems (parametrized by the input size parameter \(n\)) that can be computed with uniform Boolean circuits (with gates AND, OR, and NOT), of polynomial size in \(n\) (i.e. polynomially many gates in the input size), and \(O(\log^2 n\)) depth (i.e. the longest path from an input gate to the circuit to the output gate is in the order of \(\log^2 n\)). It is to be noted that BA is field independent, since there are no divisions in the computation of \(p_A\), and the results of the paper are field independent. BA is the fastest known algorithm for computing \(p_A\). The combinatorial interpretation of BA is based on ``loop covers introduced by \textit{L. G. Valiant} [Why is Boolean compelxity theory difficult? (1992; Zbl 0769.68050)] and clow sequences.
This page was built for publication: Berkowitz's algorithm and clow sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2783464)
