Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-105 | 9th August 2014 19:18

Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington’s Theorem


Authors: Craig Gentry
Publication: 9th August 2014 19:35
Downloads: 1418


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 NC1 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 ModpP-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.


Comment #1 to TR14-105 | 11th August 2014 12:53

a few comments

Comment #1
Authors: Oded Goldreich
Accepted on: 11th August 2014 12:53
Downloads: 412


just an attempt to slightly simplify the exposition and clarify a few issues.

ISSN 1433-8092 | Imprint