Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

Using ideas from automata theory we design a new efficient

(deterministic) identity test for the \emph{noncommutative}

polynomial identity testing problem (first introduced and studied by

Raz-Shpilka in 2005 and Bogdanov-Wee in 2005). More precisely,

given as input a noncommutative

circuit $C(x_1,\cdots,x_n)$ computing a ...
more >>>

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