ECCC-Report TR14-105https://eccc.weizmann.ac.il/report/2014/105Comments and Revisions published for TR14-105en-usMon, 11 Aug 2014 12:53:45 +0300
Comment 1
| a few comments |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2014/105#comment1just an attempt to slightly simplify the exposition and clarify a few issues.Mon, 11 Aug 2014 12:53:45 +0300https://eccc.weizmann.ac.il/report/2014/105#comment1
Paper TR14-105
| Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington’s Theorem |
Craig Gentry
https://eccc.weizmann.ac.il/report/2014/105We 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.Sat, 09 Aug 2014 19:35:45 +0300https://eccc.weizmann.ac.il/report/2014/105