Under the auspices of the Computational Complexity Foundation (CCF)

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

Revision #1
Authors: Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S
Accepted on: 6th July 2017 09:01
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
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