DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2017.38

Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings

Authors: Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, and S. Raja

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract

In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring F{X}. Prior to this work, nonassociative arithmetic computation was considered by Hrubes, Wigderson, and Yehudayoff, and they showed lower bounds and proved completeness results. We consider Polynomial Identity Testing and Polynomial Factorization in F{X} and show the following results. 1. Given an arithmetic circuit C computing a polynomial f in F{X} of degree d, we give a deterministic polynomial algorithm to decide if f is identically zero. Our result is obtained by a suitable adaptation of the PIT algorithm of Raz and Shpilka for noncommutative ABPs. 2. Given an arithmetic circuit C computing a polynomial f in F{X} of degree d, we give an efficient deterministic algorithm to compute circuits for the irreducible factors of f in polynomial time when F is the field of rationals. Over finite fields of characteristic p, our algorithm runs in time polynomial in input size and p.

Cite as

Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, and S. Raja. Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.MFCS.2017.38,
  author =	{Arvind, Vikraman and Datta, Rajit and Mukhopadhyay, Partha and Raja, S.},
  title =	{{Efficient Identity Testing and Polynomial Factorization in  Nonassociative Free Rings}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{38:1--38:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.38},
  URN =		{urn:nbn:de:0030-drops-80690},
  doi =		{10.4230/LIPIcs.MFCS.2017.38},
  annote =	{Keywords: Circuits, Nonassociative, Noncommutative, Polynomial Identity Testing, Factorization}
}

Search Results

Documents authored by Raja, S.

Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings

Abstract

Cite as

Thanks for your feedback!

Could not send message