Vikraman Arvind, Pushkar Joglekar

Based on a theorem of Bergman we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, we show the following:

(1) In the white-box setting, given an n-variate noncommutative polynomial f in F over a field F (either a ... more >>>