Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-074 | 6th July 2017 09:01

Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings

RSS-Feed




Revision #1
Authors: Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S
Accepted on: 6th July 2017 09:01
Downloads: 1039
Keywords: 


Abstract:

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)$.


Paper:

TR17-074 | 29th April 2017 10:12

Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings





TR17-074
Authors: Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S
Publication: 29th April 2017 15:21
Downloads: 934
Keywords: 


Abstract:

In 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)$.



ISSN 1433-8092 | Imprint