Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-036 | 1st August 1997 00:00

Determinant: Combinatorics, Algorithms, and Complexity

RSS-Feed




TR97-036
Authors: Meena Mahajan, V. Vinay
Publication: 10th September 1997 22:10
Downloads: 1327
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint