Noncommutative determinant is hard: A simple proof using an extension of barrington's theorem

Abstract

We show that, for many noncommutative algebras A, the hardness of computing the determinant of matrices over A follows almost immediately from Barrington's Theorem. Barrington showed how to express a NC-1 circuit as a product program over any non-solvable group. We construct a simple matrix directly from Barrington's product program whose determinant counts the number of solutions to the product program. This gives a simple proof that computing the determinant over algebras containing a non-solvable group is #P-hard or Mod pP-hard, depending on the characteristic of the algebra. To show that computing the determinant is hard over noncommutative matrix algebras whose group of units is solvable, we construct new product programs (in the spirit of Barrington) that can evaluate 3SAT formulas even though the algebra's group of units is solvable. The hardness of noncommutative determinant is already known, it was recently proven by retooling Valiant's (rather complex) reduction of #3SAT to computing the permanent. Our emphasis here is on obtaining a conceptually simpler proof. © 2014 IEEE.