ECCC-Report TR23-025https://eccc.weizmann.ac.il/report/2023/025Comments and Revisions published for TR23-025en-usWed, 15 Mar 2023 23:15:04 +0200
Paper TR23-025
| Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization |
Pushkar Joglekar,
Vikraman Arvind
https://eccc.weizmann.ac.il/report/2023/025Based 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 finite field or the rationals) as an arithmetic circuit (or algebraic branching program), computing a complete factorization of f is deterministic polynomial-time reducible to white-box factorization of a noncommutative bivariate polynomial g in F; the reduction transforms f into a circuit for g (resp. ABP for g), and given a complete factorization of g the reduction recovers a complete factorization of f in polynomial time. We also obtain a similar deterministic polynomial-time reduction in the black-box setting.
(2) Additionally, we show over the field of rationals that bivariate linear matrix factorization of 4 x 4 matrices is at least as hard as factoring square-free integers. This indicates that reducing noncommutative polynomial factorization to linear matrix factorization (as done in our recent work [AJ22]) is unlikely to succeed over the field of rationals even in the bivariate case.
In contrast, multivariate linear matrix factorization for 3 x 3 matrices over rationals is in polynomial time.Wed, 15 Mar 2023 23:15:04 +0200https://eccc.weizmann.ac.il/report/2023/025