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.