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

by Craig Gentry

Oded's comments

I have mixed feelings regarding recommending this paper. On the one hand, it presents an ingenious proof of an interesting result. On the other hand, I don't like the exposition. It is not that the paper is carelessly written - on the contrary; but I find the organization and presentation geared to a different type of people (i.e., different than myself). Specifically, in my opinion, it would have been better to move as fast as possible to the proof of Thm 5 (and Cor 3), and postpone the generalizations to later. In the time being (i.e., untill a revision is provided...), I recommend focusing on Section III.B, after reading Sections I.B and II.D. (I found Sec III.A and most of Sec II not really helpful, and would recommend skipping them in first reading. The core is really Sec III.B, whereas Sec I.B and part of Sec II.D may be a helpful guide towards it.)

As said, the proof is ingenious. It is very simple once understood, but it is quite a mystery how one may come to invent it. Hence, unless I miss some relevant background that may lead in a natural way to that invention, it seems that only the word `ingenious' can describe it.

The proof of the mian result consists of a construction of a matrix, described in the first paragraph of Sec III.B (you will need the definition of $\inp(i)$, which appears in Sec. I.B); for every product program a corresponding matrix is constructed. This is followed a slightly laconic proof (of Thm 5) that shows that the value of the determinant (or permanent) of this matrix equals the sum of the values of the product program (which in turn yields the desired count). It would be a good service to elaborate a bit on this proof, and then provide a digest - my initial attempt in that direction can be found HERE.

The original 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 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.

See ECCC TR14-105.


Back to list of Oded's choices.