ECCC-Report TR97-036https://eccc.weizmann.ac.il/report/1997/036Comments and Revisions published for TR97-036en-usWed, 10 Sep 1997 22:10:21 +0300
Paper TR97-036
| Determinant: Combinatorics, Algorithms, and Complexity |
Meena Mahajan,
V Vinay
https://eccc.weizmann.ac.il/report/1997/036We prove a new combinatorial characterization of the
determinant. The characterization yields a simple
combinatorial algorithm for computing the
determinant. Hitherto, all (known) algorithms for
determinant have been based on linear algebra. Our
combinatorial algorithm requires no division and works over
arbitrary commutative rings. It also lends itself to
efficient parallel implementations.
It has been known for some time now that the complexity
class GapL characterizes the complexity of computing the
determinant of matrices over the integers. We present a
direct proof of this characterization.
Wed, 10 Sep 1997 22:10:21 +0300https://eccc.weizmann.ac.il/report/1997/036