Craig Gentry

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 ... more >>>