ECCC-Report TR17-074https://eccc.weizmann.ac.il/report/2017/074Comments and Revisions published for TR17-074en-usThu, 06 Jul 2017 09:01:20 +0300
Revision 1
| Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings |
Vikraman Arvind,
Rajit Datta,
Partha Mukhopadhyay,
Raja S
https://eccc.weizmann.ac.il/report/2017/074#revision1 In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this
work, nonassociative arithmetic computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10], and they showed lower bounds and proved completeness results. We consider Polynomial Identity Testing (PIT) and polynomial factorization over $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$ and show the
following results.
(1) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $f\in \mathbb{F} \{x_1,x_2,\ldots,x_n\}$ of degree $d$, we give a deterministic
$poly(n,s,d)$ algorithm to decide if $f$ is identically zero polynomial or not. Our result is obtained by a suitable adaptation of the PIT algorithm of Raz-Shpilka [RS05] for noncommutative ABPs.
(2)Given an arithmetic circuit $C$ of size $s$ computing a polynomial $f\in \mathbb{F} \{x_1,x_2,\ldots,x_n\}$ of degree $d$, we give an efficient deterministic algorithm to compute circuits for the
irreducible factors of $f$ in time $poly(n,s,d)$ when $\mathbb{F}=\mathbb{Q}$. Over finite fields of characteristic $p$, our algorithm runs in time
$poly(n,s,d,p)$.Thu, 06 Jul 2017 09:01:20 +0300https://eccc.weizmann.ac.il/report/2017/074#revision1
Paper TR17-074
| Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings |
Vikraman Arvind,
Rajit Datta,
Partha Mukhopadhyay,
Raja S
https://eccc.weizmann.ac.il/report/2017/074In this paper we study arithmetic computations over non-associative, and non-commutative free polynomials ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this work, the non-associative arithmetic model of computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10]. They were interested in completeness and explicit lower bound results.
We focus on two main problems in algebraic complexity theory: Polynomial Identity Testing (PIT) and polynomial factorization over $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. We show the following results.
(1) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $f\in \mathbb{F} \{x_1,x_2,\ldots,x_n\}$
of degree $d$, we give a deterministic $poly(n,s,d)$ algorithm to decide if $f$ is identically zero polynomial or not.
Our result is obtained by a suitable adaptation of the PIT algorithm of Raz-Shpilka [RS05] for non-commutative ABPs.
(2) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $f\in \mathbb{F}\{x_1,x_2,\ldots,x_n\}$ of degree $d$, we give an efficient deterministic algorithm to compute the circuits for the irreducible factors of $f$ in time $poly(n,s,d)$ when $\mathbb{F}=\mathbb{Q}$.
Over finite fields of characteristic $p$, our lgorithm runs in time $poly(n,s,d,p)$.Sat, 29 Apr 2017 15:21:37 +0300https://eccc.weizmann.ac.il/report/2017/074